 # KDCT02 - Editorial

**

**
Contest

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   + 2^0*(a + a + ... + a[n]) * (n-1)
+ T   + (a + a + ... + a[n])*(n)
``````

where T = 0

Now, to simplify the addition, let us use an array S where S[n] is the presum of a 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)
``````

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

//