**

## PROBLEM LINKs

**

Contest

## DIFFICULTY

EASY

## PROBLEM

In simple terms, the question can be rewritten as:

Consider an array, A, of length n. We can split A into contiguous segments and store them as another array, B. We consider the value of such a segment in some array B to be (sum of all numbers in segment) * (length of segment), and we consider the total value of some array to be the sum of the values for all segments in that array.

## EXPLAINATION

The simplest solution is the recursive brute force approach. But the required complexity is atleast O(n^2), so this approach doesnâ€™t pass all test cases. On examining the pattern carefully, we can arrive at the following recurrence relation:

```
T[n] = T[n-1] + 2^(n-2)*(a[n]) // T[n-1] forms 2^(n-2) subsets
+ T[n-2] + 2^(n-3)*(a[n-1] + a[n]) * 2
+ T[n-3] + 2^(n-4)*(a[n-2] + a[n-1] + a[n]) * 3
+ ...
+ T[1] + 2^0*(a[2] + a[3] + ... + a[n]) * (n-1)
+ T[0] + (a[1] + a[2] + ... + a[n])*(n)
```

where T[0] = 0

Now, to simplify the addition, let us use an array S where S[n] is the presum of a[0] to a[n]. So any sum from a[i] to a[j] is S[j] - S[i-1].

Now the solution become something like:

```
T[n] = 2*T[n-1] + 2^(n-1)*S[n] + (2^(n-1)-1)*a[n]
- (2^(n-2)*S[n-1] + 2^(n-3)*S[n-2] + ... + S[1])
```

Thus, the required sum can be calculated in O(n^2) time.