William and Summation

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

William is given an array of N integers a_1, a_2, \dots, a_n. He then must pick one contiguous segment [L, R] (1 \le L \le R \le N) and multiply all values on that segment (a_L, \dots, a_R) by -1.

His goal is such that after modifying this segment, the sum of the prefix sums is minimized. This value can be represented as:

\displaystyle \sum_{i=1}^N \sum_{j=1}^i a_j

Output the minimal value attainable under the given terms.

Input Specification

The first line consists of a single integer N (1 \le N \le 10^5).

The next line contains N space-separated integers a_1, a_2, \dots, a_N (-1\,000 \le a_i \le 1\,000).

Subtask 1 [20%]

1 \le N \le 2000

Subtask 2 [80%]

No further constraints.

Output Specification

Output a single integer, the minimal value attainable of the expression outlined above.

Sample Input 1

4
1 -2 100 -5

Sample Output 1

-207

Explanation for Sample 1

If the segment [3,3] was modified our array will become: [1, -2, -100, -5].

The prefix sum of the modified array is:

[1, -1, -101, -106]

Thus the answer would be the sum of the prefix sum of all elements:

\text{ans} = 1 + (-1) + (-101) + (-106) = -207

The value -207 is the minimum attainable answer.

Sample Input 2

5
-10 7 -2 -2 10

Sample Output 2

-78

Comments

There are no comments at the moment.