SumOfPower

SRM 626 · 2013-12-22 · by lg5293

SRM 626 · 2013-12-22 · by lg5293 · Brute Force

Show categories

Class Name: SumOfPower

Return Type: int

Method Name: findSum

Arg Types: (vector<int>)

Problem Statement

You are given a int[] array. At any moment, you may choose a nonempty contiguous subsequence of array. Whenever you do so, you will gain power equal to the sum of all elements in the chosen subsequence.

You chose each possible contiguous subsequence exactly once, each time gaining some power. Compute and return the total amount of power you gained.

Constraints

array will contain between 1 and 50 elements, inclusive.
Each element in array will be between 1 and 100, inclusive.

Examples

{1,2}
Returns: 6

We have the following three contiguous subsequences: {1} => 1 {2} => 2 {1,2} => 3 Thus, the sum of all possible powers is 1+2+3=6.

{1,1,1}
Returns: 10

A 3-element sequence has 6 possible nonempty contiguous subsequences. For the sequence {1,1,1} these are the subsequences: {1}, {1}, {1}, {1,1}, {1,1}, and {1,1,1}. Their sums are 1, 1, 1, 2, 2, and 3. If you choose each of them once, the total power you'll gain is 1+1+1+2+2+3 = 10.

{3,14,15,92,65}
Returns: 1323

{1,2,3,4,5,6,7,8,9,10}
Returns: 1210

{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}
Returns: 714000

Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SumOfPower with a public method int findSum(vector<int> array) · 61 test cases · 2 s / 256 MB per case