DMOPC '20 Contest 2 P6 - Unfair Game

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem types

Two players, A and B, are playing a game on a row of N coins, each with a positive integer value a_i. Player A goes first and can take any coin. Then, player B must take a coin adjacent to the coin that A chose, or must skip his turn if there are no coins adjacent to the spot that A chose. The players then alternate turns, where A can always take any remaining coin but B must take a coin adjacent to the spot A just chose or skip his turn if this is not possible. The game ends when all the coins are taken by one of the two players. Both players want to maximize the total sum of the values of the coins they have at the end.

The players will play the game Q+1 times, where after each game all the coins are returned to their original positions in the row and a new coin with value b_i is added to the right end of the row.

Assuming they play optimally, calculate the total sum that player A will get in each game.

Constraints

1 \le a_i \le 10^9 and 1 \le b_i \le 10^9 for all i.

Subtask 1 [10%]

1 \le N \le 20, Q = 0

Subtask 2 [10%]

1 \le N \le 200, Q = 0

Subtask 3 [10%]

1 \le N \le 200, 0 \le Q \le 200

Subtask 4 [15%]

1 \le N \le 2\,000, Q = 0

Subtask 5 [15%]

1 \le N \le 2\,000, 0 \le Q \le 2\,000

Subtask 6 [20%]

1 \le N \le 200\,000, Q = 0

Subtask 7 [20%]

1 \le N \le 200\,000, 0 \le Q \le 200\,000

Input Specification

The first line contains two space-separated integers: N and Q.

The second line contains N space-separated integers: a_1, a_2, \dots, a_N.

The third line contains Q space-separated integers: b_1, b_2, \dots, b_Q.

If Q = 0, the third line is empty.

Output Specification

Output Q+1 lines: the total sum that player A will get in each game.

Sample Input 1

5 1
3 1 4 2 5
6

Sample Output 1

12
13

Explanation for Sample Output 1

Here is one way the first game could proceed:

  • First, player A takes the coin with a value of 4.
  • Then, player B must take either the coin with value 1 or the coin with value 2. He decides to take the coin with value 2.
  • Then, player A takes the coin with value 5. There are no untaken coins adjacent to this coin, so player B must skip his turn.
  • Finally, player A takes the coin with value 3. Player B must take the only remaining coin with value 1, and the game ends with A getting a total sum of 4+5+3 = 12.

The second game is played on the row [3,1,4,2,5,6], and player A can get a total sum of 13 if both players play optimally.

Sample Input 2

10 0
27 18 28 18 28 45 90 45 23 53

Sample Output 2

243

Comments

There are no comments at the moment.