CCO Preparation Test 7 P1 - Game of Stone - DMOJ: Modern Online Judge

CCO Preparation Test 7 P1 - Game of Stone

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 1.4s

Memory limit: 128M

Author:

bruce

Problem types

Allowed languages

C, C++, Java, Pascal

Joey and Jason are playing a stone game. There are $N$ ~N~ piles of stones in a line, where the pile $i$ ~i~ has $a_i$ ~a_i~ ( $a_i \ge 0$ ~a_i \ge 0~) stones. The rules of this game are as follows:

In each turn, a player must take a whole pile of stone.
If a player wants to take one pile, one of the adjacent piles (neighbors) must be empty. Notice: since the $N$ ~N~ piles are placed in one line, pile $1$ ~1~ is only adjacent with pile $2$ ~2~, pile $2$ ~2~ is adjacent with pile $1$ ~1~ and pile $3$ ~3~, …, and pile $N$ ~N~ is only adjacent with pile $N-1$ ~N-1~.
When all piles are empty, the game is finished. The player who gets the most stones will be the winner.

Joey and Jason are both smart. So, they will always take the optimal strategy. Since Joey is younger than Jason, he will always go first. Could you please write a program to output the number of stones Joey and Jason will get?

Input Specification

The first line of input contains $N$ ~N~ ( $2 \le N \le 10^6$ ~2 \le N \le 10^6~), the number of piles.

The second line of input contains $N$ ~N~ non-negative integers, $a_i$ ~a_i~ ( $0 \le a_i \le 10^8$ ~0 \le a_i \le 10^8~), the number of stones in pile $i$ ~i~. It is guaranteed that there is at least one pile of stone is empty at the beginning of the game.

Output Specification

Output the number of stones Joey and Jason will get in one line. It is guaranteed that the output does not exceed $2^{63} - 1$ ~2^{63} - 1~.

Sample Input

8
1 2 0 3 7 4 0 9

Sample Output

17 9

Explanation

Joey and Jason both take the optimal strategy, and they will take stones in the order 9, 2, 1, 4, 7, 3. Finally, Joey will get $9+1+7 = 17$ ~9+1+7 = 17~ stones, while Jason will get $2+4+3 = 9$ ~2+4+3 = 9~ stones.

Comments

0

root commented on Sept. 27, 2016, 12:54 a.m. ← edited →

Why limit the languages?

0

nathanl3 commented on Sept. 27, 2016, 2:50 p.m. ← edited →

Because this is CCO Preparation