Michael and Charging Stations
Contest: Codeforces Round 433 (Div. 1, based on Olympiad of Metropolises)
Difficulty rating: 2400
Tags: binary search, dp, greedy

Michael has just bought a new electric car for moving across city. Michael does not like to overwork, so each day he drives to only one of two his jobs.

Michael's day starts from charging his electric car for getting to the work and back. He spends 1000 burles on charge if he goes to the first job, and 2000 burles if he goes to the second job.

On a charging station he uses there is a loyalty program that involves bonus cards. Bonus card may have some non-negative amount of bonus burles. Each time customer is going to buy something for the price of x burles, he is allowed to pay an amount of y (0 ≤ y ≤ x) burles that does not exceed the bonus card balance with bonus burles. In this case he pays x - y burles with cash, and the balance on the bonus card is decreased by y bonus burles.

If customer pays whole price with cash (i.e., y = 0) then 10% of price is returned back to the bonus card. This means that bonus card balance increases by $$\frac{\pi}{10}$$ bonus burles. Initially the bonus card balance is equal to 0 bonus burles.

Michael has planned next n days and he knows how much does the charge cost on each of those days. Help Michael determine the minimum amount of burles in cash he has to spend with optimal use of bonus card. Assume that Michael is able to cover any part of the price with cash in any day. It is not necessary to spend all bonus burles at the end of the given period.

Input format:
The first line of input contains a single integer n (1 ≤ n ≤ 300 000), the number of days Michael has planned.

Next line contains n integers a1, a2, ..., an (ai = 1000 or ai = 2000) with ai denoting the charging cost at the day i.

Output format:
Output the minimum amount of burles Michael has to spend.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first sample case the most optimal way for Michael is to pay for the first two days spending 3000 burles and get 300 bonus burles as return. After that he is able to pay only 700 burles for the third days, covering the rest of the price with bonus burles.

In the second sample case the most optimal way for Michael is to pay the whole price for the first five days, getting 1000 bonus burles as return and being able to use them on the last day without paying anything in cash.

Example input:
3
1000 2000 1000

Example output:
3700

Example input:
6
2000 2000 2000 2000 2000 1000

Example output:
10000

Editorial:
Before solving problem one observation is required: suppose at day i we have xi bonuses. Then exists optimal solution, which spends 0 or min(ai, xi) bonuses every day.
It's quite easy to proof: suppose we have some optimal solution and i is a first day, when neither 0 nor min(ai, xi) bonuses were spent. If i is a last day on which non-zero amount of bonuses was spent, we can notice that solution spending min(ai, xi) bonuses that day is more optimal, so first solution was optimal. So let's consider next day after i, when non-zero amount of bonuses was spent, say j, and amount of bonuses spent at day j is sj (Also, amount of bonuses spent on day i is si). Let's look at solution that spends si + min(si - min(ai, xi), sj) bonuses at day i and sj - min(si - min(ai, xi), sj). That solution is still correct and still optimal, but it spends min(ai, xi) at day i or 0 at day j. Anyway this operation increases first day i when neither i nor min(ai, xi) bonuses were spent or first day j after it, when non-zero amount of burles were spent. But we can't increase i or j infinitely, so, after some iterations of such transformation, solution, spending 0 or min(ai, xi) bonuses in each day.
To make an O(n2) solution it's possible to consider dynamic programming approach: let dpi, j be minimum amount of money that is possible to spend at first i days to pay for all chargings and have 100·j bonuses on card. At first, dp0, 0 = 0 and dpi, j = ∞. Then we can easy calculate all states going through all states with something like this code:
Of course, j can be up to 2·n, because at each day it's possible to earn at most 2 bonuses.
To make this solution faster let's consider the following observation: there exists an optimal solution, which never has more 3000 bonuses on bonus card. To proof it let's first proof following lemma:
Lemma 1: There exists an optimal solution which spends only 0 or ai bonuses at day i if there are at least 3000 bonuses at card at the beginning of day i.
Lemma 1 proof: Let's introduce some designations. Let xi be amount of bonuses at the beginning of day i and si be amount of bonuses spent at day i. Also let's call day i "fractional" if si ≠ 0 and si ≠ ai, and call day i "interesting" if si ≠ 0. Let's proof lemma2 and lemma3 at first:
Lemma 2: Assume xi ≥ 3000 and j — next after i interesting day and k — next after j interesting day. Then there exists an optimal solution in which k is not a fractional day or j is not a fractional day.
Lemma2 proof: Suppose is some optimal solution j and k are fractional days. Let's consider a solution spending sj + min(sk, aj - s{j}) bonuses at day j and sk - min(sk, aj - s{j}) at day k. This solution is still correct, because xi ≥ 3000, so for days j and k there is enough bonuses and still optimal. Lemma2 is proved.
Lemma 3: Assume xi ≥ 3000 and j — next after i interesting day. Then there exists an optimal solution is which j is not a fractional day.
Lemma 3 proof: Consider some optimal solution with fractional day j. At first let's proof that j is not last interesting day. Suppose, j is last interesting day in solution. But we can make a solution that spends ai bonuses at day i (because ai ≤ 3000) and it will be more optimal. Contradiction. So there exists next after j interesting day. Let's call it k. Let's consider 2 cases:
Case 1 (aj = 1000): Let's spend consider solution spending 1000 bonuses at day j and ak - (1000 - sj)) at day k. It's still correct and optimal but j is not a fractional day.
Case 2 (aj = 2000): There are two subcases:
Case 2.1 (ak = 2000): Let's spend consider solution spending 2000 bonuses at day j and ak - (2000 - sj)) at day k. It's still correct and optimal but j is not a fractional day.
Case 2.2 (ak = 1000): Let's proof, k is not last interesting day. Assume k is last interesting day. Consider a solution spending 2000 bonuses at day j and 1000 bonuses at day k. It's correct but more optimal that initial solution. Conrtadiction. Now let p be next after k interesting day (k is not a fractional day by lemma2). If 2000 - aj ≤ 1000 we can consider solution which spends 2000 bonuses at day j, 1000 - (2000 - ak) bonuses at day k and sp bonuses at day p. If 2000 - sj > 1000 let's consider a solution which spends sj + 1000 bonuses at day j, 0 bonuses at day k and sp at day p. But by lemma2 sp = ap, so we can consider solution that spends 2000 bonuses at day j 0 bonuses at day k and ap - (2000 - sj - ak) at day k. All of these solutions are correct and optimal.
Lemma 1 proof (end): At first, of course there is at least one interesting day after i (Otherwise, it's more optimal to charge at day i using bounses, but in initial solution si = 0 because xi - 1 ≤ 3000 and xi > 3000). Let's call that day j and by lemma3 j is not fractional day. Let's consider 4 cases now:
Case 1: (ai = 1000, aj = 1000). Let's consider a solution with si = 1000 and sj = 0. It's correct and still optimal, but xi ≤ 3000.
Case 2: (ai = 2000, aj = 2000). Same as case1.
Case 3: (ai = 2000, aj = 1000). Let's consider 2 subcases:
Case 3.1: j is not last interesting day. Let k be next interesting day. It ak = 1000 consider a solution spending 2000 bonuses at day i, 0 bonuses at days j and k. It's still correct and optimal, but xi ≤ 3000. If ak = 2000 consider a solution a spending 2000 bonuses at day i, 1000 bonuses at day j and 0 bonuses at day k. It's correct and optimal too, and xi ≤ 3000 too.
Case 3.2: j is last interesting day. Let's construct solution this way. At first let's set si = 1000 and sj = 0. Then let's iterate over all ineteresting days after j, say k, in order in increasing time and set si = si + min(2000 - si, sk), sk = sk - min(2000 - si, sk). If after this process we still have some bonus left just add it to si. At the end, si will be equal 2000 because we spent all bonuses, solution will still be correct and optimal, but xi ≤ 3000.
Case 4: (ai = 1000, aj = 2000). Let p be last day before i with sp ≠ 0. If ap = 1000 consider a solution with sp = 0, si = 0, sj = 2000. It's correct, optimal and xt ≤ 3000 for each t ≤ i. If ap = 2000, consider a solution with sp = 2000, si = 0, sj = 0. It's correct, optimal and xt ≤ 3000 for each t ≤ i, too.
So for all cases we can make correct and optimal solution such there is no xi ≤ 3000 for all i, or number of first day with xi > 3000 increases, but it can't increase forever, so after some amount of opereations solution with xi ≤ 3000 for all i will be constructed.
Because of this fact we can consider dynamic programming approach described before but notice, that we should consider only states with j ≤ 30. It will have O(n) complexity. Moreover, looking at states with j = 30 is required. It's possible to make a test on which solution, that looks at states with j ≤ 29 will be incorrect.