Breakfast Buffet

Time limit1sMemory limit1024 MB

Summary

Pär and Oskar alternate eating dishes in a row, and the task is the largest sum of ratings Pär can guarantee for himself whatever Oskar does.

Level: Medium6 of 10
Topics: Game theory, Implementation, Prefix sum
Solved: No attempts yet

Statement

Pär and Oskar are going to eat at a breakfast buffet. The buffet has $N$ different dishes numbered from $1$ to $N$ , placed in a row on a long table. Pär thinks some dishes are tastier than others, so he has given each dish a rating. Dish $i$ has rating $a_i$ .

At the start, Pär picks a dish and eats it. Then Oskar picks a dish and eats it. Both are very hungry, so they always eat up everything that is left of the dish they picked.

Once both have eaten, they pick a new dish. They dislike walking, so they always pick a dish right next to the one they just ate. That is, if someone just ate dish $i$ , they can pick dish $i-1$ or dish $i+1$ . If the new dish has not been eaten yet, the person who picked it eats it. If it has already been eaten, that person must wait until their next turn. In every turn, Pär chooses first.

Pär does not want to be picky, so he will not skip over a dish that is still left. He is also very hungry, so he always wants to eat at least one dish. After eating a dish, Pär and Oskar can each shout "Nu är jag mätt!" and leave the breakfast without eating anything more.

The breakfast ends when all dishes have been eaten or both have left. Pär's satisfaction depends on how good the dishes he ate are. We define his satisfaction as the sum of the ratings of all dishes he ate.

Pär does not know how Oskar will behave. So he wants to know the maximum satisfaction he can guarantee for himself without knowing anything about Oskar's behavior.

Examples4

Example 1
Input
```
3
3 5 2
```
Expected output
```
7
```
Example 2
Input
```
5
3 5 2 1 2
```
Expected output
```
8
```
Example 3
Input
```
6
-1 3 -2 5 -1 2
```
Expected output
```
6
```
Example 4
Input
```
3
-1 -2 -3
```
Expected output
```
-1
```