Bear and Bowling
Contest: Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1)
Difficulty rating: 3200
Tags: data structures, greedy

Limak is an old brown bear. He often goes bowling with his friends. Today he feels really good and tries to beat his own record!

For rolling a ball one gets a score — an integer (maybe negative) number of points. Score for i-th roll is multiplied by i and scores are summed up. So, for k rolls with scores s1, s2, ..., sk, total score is $$\sum_{i=1}^{k} i \cdot s_i$$. Total score is 0 if there were no rolls.

Limak made n rolls and got score ai for i-th of them. He wants to maximize his total score and he came up with an interesting idea. He will cancel some rolls, saying that something distracted him or there was a strong wind.

Limak is able to cancel any number of rolls, maybe even all or none of them. Total score is calculated as if there were only non-canceled rolls. Look at the sample tests for clarification. What maximum total score can Limak get?

Input format:
The first line contains single integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers a1, a2, ..., an (|ai| ≤ 107) - scores for Limak's rolls.

Output format:
Print the maximum possible total score after choosing rolls to cancel.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
In first sample Limak should cancel rolls with scores  - 8 and  - 3. Then he is left with three rolls with scores  - 2, 0, 5. Total score is 1·( - 2) + 2·0 + 3·5 = 13.

In second sample Limak should cancel roll with score  - 50. Total score is 1·( - 10) + 2·20 + 3·( - 30) + 4·40 + 5·60 = 400.

Example input:
5
-2 -8 0 5 -3

Example output:
13

Example input:
6
-10 20 -30 40 -50 60

Example output:
400

Editorial:
FIRST PART - greedy works
We will add (take) elements to a subsequence one by one. Adding number x, when we have k - 1 taken numbers on the left, increases result by k·x + suf where suf is sum of taken numbers on the right. Let's call this added value as the Quality of element x.
We will prove correctness of the following greedy algorithm. We take element with the biggest Quality till there are no elements left. For every size of a subsequence (number of taken elements) we will get optimal score.
(lemma) If ai > aj and i < j, we won't take aj first.
Proof. Let's consider a moment when we don't fulfill the lemma for the first time. If there are no taken numbers between ai and aj, we have Qi = k·ai + suf > k·aj + suf = Qj so ai is a better choice. For taken numbers between ai and aj - each number x changes Qi by x and Qj by aj. We'll see that x > aj so Qi will remain greater than Qj. If ai > x, the lemma (fulfilled till now) says that x wasn't taken before ai - it can't be true because x is taken and ai is not. So indeed x ≥ ai > aj.
Let's assume that our greedy strategy is not correct. Let's consider first moment when we take some element aj and for some s we can't get optimal subsequence with size s by taking more elements (using any strategy). Let A denote a set of elements taken before. So there is no way to add some more elements to set A + aj and achieve optimal score with size s. But it was possible just before taking aj so there is a subset of remaining elements B that |A + B| = s and set A + B is the best among sets with size s. Note that B can't be empty.
(case 1 - B contains at least one element on the left from aj) Let ai denote last element from B that i < j (here "last" means "with the biggest i"). Our strategy wanted aj before elements from B so we know from lemma that ai ≤ aj. It will turn out that replacing ai with aj (in set A + B) doesn't decrease the score so taking aj is acceptable. Note that replacing an element with another one doesn't change size of a set/subsequence.
In moment of choosing aj it had the biggest quality so then Qj ≥ Qi. Now in A + B there are new elements, those in B. Let's imagine adding them to A (without ai and aj). Each new element x on the right change both Qi and Qj by x. Elements on the left change Qi by ai and Qj by aj (note that ai ≤ aj). And there are no elements between ai and aj. Now, taking ai would give us set A + B but Qj remains not less than Qi so we can take aj instead.
(case 2 - B contains only elements on the right from aj) Similarly, we can replace ai with closest aj from set B. As before, elements on the right change Qi and Qj by the same value.
SECOND PART - how to implement it
First, let's understand $${ \mathcal { O } } ( n { \sqrt { n \log n } } )$$ solution. We divide a sequence into $$\sqrt{n}$$ Parts. When choosing the best candidate in a Part, we want to forget about other Parts. It's enough to remember only x and suf - number of taken elements on the left (in previous Parts) and sum of elements on the right (in next Parts). x affects choosing the best element in a Part, suf doesn't (but we need this constant to add it to result for best candidate). For a Part we want to have hull with $$\sqrt{n}$$ linear functions of form ai·x + b. With binary search we can find the best element in $$O(\sqrt{n} \log n)$$ and then construct new hull for this Part in $$O(\sqrt{n} \log n)$$.
We can remove $$\log n$$ from complexity. First, binary search can be replaced with pointers - for each Part initially we set a pointer at the beginning of Part. To find best candidate in Part, we slowly move pointer to the right (by one). Complexity is amortized $$O(n\sqrt{n})$$. And we can sort linear functions ai·x + b by angle only once because value ai doesn't change - then constructing a hull is only $$O(\sqrt{n})$$. Note that when rebuilding a hull, we must set pointer to the beginning of Part.
So we have $${ \mathcal { O } } ( n \log n + n { \sqrt { n } } )$$.
TODO. I think that it can be done in n*polylog(n).
—— DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——-
—— DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——-
—— DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——-
—— DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——-
—— DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——-
—— DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——- DO NOT READ THINGS BELOW ——-
To make this tutorial shorter and more understandable, I won't distinguish things like positive and non-negative. Or greater and greater-or-equal. You can think about these details in proofs by yourself.
FIRST PART - greedy works
We will add elements to a subsequence one by one. Adding element x, when we have k - 1 other taken elements on the left, increases result by k·x + suf where suf is sum of elements on the right from x. Let's take a look at two lemmas and then we will form a solution.
(1) Every suffix of subsequence has positive sum of elements. Otherwise, shortest negative suffix starts with negative number and removing this number would increase a result.
(2) All positive elements belong to subsequence. Let's say we don't take a positive number x and we have final subsequence. Then from (1) we know that sum of taken elements on the right is positive, so suf > 0 and x > 0. It means that k·x + suf > 0.
First, let's take all positive numbers. Now, let's consider following strategy (to choose negative numbers). We add element with the biggest added value (k·x + suf) till this value is positive. We'll prove that this greedy approach works and produces an optimal subsequence.
(3) If a[i], a[j] < 0 and a[i] > a[j] and i < j, we won't take a[j] before a[i]. E.g. if a[5] =  - 20 and a[12] =  - 80, we won't take  - 80 first. Again, we will use contradiction. In some moment we break the rule (lemma) for the first time. Let's say we take a[12] =  - 80 before a[5] =  - 20 and we didn't break a rule before.
Let x denote number of taken elements on the left from a[5] and Sx denote their sum. Similarly, let y and Sy denote number and sum of taken elements between a[5] and a[12]. Finally, let z and Sz denote the same for elements on the right from a[12].
Taking a[5] =  - 20 would give us  - 20(x + 1) + Sy + Sz. Taking a[12] =  - 80 gave us  - 80(x + y + 1) + Sz. We prefered  - 80 so second added value must be greater than the first one.
- 80(x + y + 1) + Sz >  - 20(x + 1) + Sy + Sz
- 80(x + y + 1) >  - 20(x + 1) + Sy
- 80y - 60(x + 1) > Sy
Sy <  - 80y - 60(x + 1) <  - 80y
$$\frac{S_y}{y} < -80$$
The mean value in segment between a[5] and a[12] is lower than  - 80 so there are some taken numbers lower than  - 80. But it means that somewhen before we took (from that segment) something lower than  - 20. So we broke a rule before - taking that element before a[5].
We proved (3).
Ok, we take elements according to our strategy. If it's not optimal, one of the following must be true:
(A) We took good elements but we stopped taking elements to soon. This option never happens because we stop when we can't add positive value to the result. And for fixed element (waiting for being taken) added value only decreases in time. Here we use fact that we take only negative numbers.
(B) There is some first moment when we take an element but we should not - that there is no strategy leading to good result. It means that there is no subset of remaining elements leading to result equal to optimal one. Let's deal with this case.
We take element a[i] =  - 80 because it has the biggest value k·a[i] + suf =  - 80k + suf. But optimal subsequence instead of a[i] contains some Extra (other) elements, not taken before. There are at least two Extra elements (think why). Let's look at the Extra element which is left neighbour of a[i] (closest Extra element on the left). Let a[j] denote it. a[j] < a[i] because of (3), so e.g. a[j] =  - 90. It turns out that it's good to exchange this element for a[i] =  - 80. Our greedy strategy told us to do it before so added value for a[i] was bigger. Later some more numbers on the right appeared but they affected "added value" of both a[i] and a[j] by the same number. And some more numbers appeared on the right and each decreased "added value" of a[i] by  - 80 and "added value" of a[j] by  - 90. So they made choosing a[j] even worse than before - so it's better to change it for a[i].
But we assumed that there is some Extra element on the left. Maybe all Extra elements are on the right. Then the same thinking will do a job for a right neighbour of a[i] - new numbers will only make this neighour worse.
And... we proved correctness of greedy strategy.