Problem F
Cookie Game
Gustav and Oskar found some cookies in the base, so they put them in a line on the table and numbered them $1$ to $n$ from left to right. Cookie number $i$ takes $a_ i$ bites to eat. Gustav and Oskar want to eat the cookies, but they couldn’t agree on how to divide the cookies between themselves, so they decided to play a game. They will take turns playing a move. A move consists of either
-
taking a cookie from the table, or
-
taking a bite from a previously taken cookie
If Gustav or Oskar take a cookie, they must finish eating it before taking another one. When there are no cookies left and one player has finished his last cookie, he has to wait while the other player finishes his.
Oskar’s strategy is to always take the leftmost cookie (lowest index) when he can take a new cookie. Gustav makes the first move and wants to eat as many cookies as possible. How many cookies can he eat if he knows about Oskar’s strategy and plays optimally?
Input
The first line contains the integer $n$. The second line contains the $n$ space separated integers $a_ i$ ($1 \leq a_ i$).
Output
Output one integer, the maximum number of cookies Gustav can get.
Scoring
|
Group |
Points |
Constraints |
|
$1$ |
$25$ |
$n \leq 20, a_ i \leq 20$ |
|
$2$ |
$20$ |
$n \leq 75, a_ i \leq 75$ |
|
$3$ |
$15$ |
$n \leq 250, a_ i \leq 10^9$ |
|
$4$ |
$40$ |
$n \leq 5000, a_ i \leq 10^9$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 1 1 1 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 8 8 1 1 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 7 2 9 1 4 4 |
4 |
