Problem B
Thirsty Cow
The water level has been changing a lot lately, but there is a thirsty cow by the water that could change that!
You have received information regarding what the water level will be the coming $N$ days. On any given day $i$, the water level will be $a_i$. The cow can drink all water on a day if the water level is at least zero. If you let the thirsty cow drink water any given day, the cow will greedily drink all $a_i$ water units. By letting the thirsty cow drink, it will also decrease the water level of all days after that by $a_i$ units. The water level may become negative on future days, which means that the cow cannot drink any water on those days.
Since the thirsty cow is extremely thirsty, the cow wants to drink as much water as possible in total over all $N$ days. Could you help the thirsty cow figure out how much it could drink if it decides when to drink optimally?
Input
The first line contains an integer $N$ ($1 \leq N \leq 3 \cdot 10^5$), the number of days as described above.
The second line contains $N$ integers, $a_1, a_2, \dots , a_N$ $(1 \leq a_i \leq 10^9)$, where $a_i$ denotes the water level on the $i$-th day.
Output
Print an integer: the maximum amount of water units the thirsty cow can drink across all $N$ days.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$19$ |
$N, a_i \leq 200$ |
|
$2$ |
$29$ |
$N \leq 3000$ |
|
$3$ |
$52$ |
No additional constraints. |
Explanation of Samples
In sample $1$, the cow could drink on the first day. The water levels the coming days are then $[-5,0]$. This means that it cannot drink any more water. Therefore, it drinks $10$ water units total, which is optimal. There are other optimal drinking schedules; drinking on both days $2$ and $3$ works.
In sample $2$, one optimal way of drinking is to drink on days $2$, $4$ and $5$, which results in the cow drinking $10$ units of water. If this schedule is followed, the water levels will be as follows. For each day, the water levels of the coming days are shown, after the cow has drunk the water (if it drinks water on said day).
-
Day $1$: $[3,2,9,10]$
-
Day $2$: $[-1,6,7]$
-
Day $3$: $[6,7]$
-
Day $4$: $[1]$
-
Day $5$: $[]$
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 3 10 |
10 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 5 3 2 9 10 |
10 |
