All problems

Treasure Row Duel

Medium · dynamic programming

Two explorers, Ada and Ben, find a row of treasure chests. The chest at position i is worth prizes[i]; a value below zero is a cursed chest that costs its taker that much. Ada plays first and they take turns.

On a turn, the player must take chests from the left end of the row that is still left. The player picks one number t from the list takes and takes exactly the t leftmost chests, adding their values to their own score. A player may only pick a t that is not larger than the number of chests left. If *no* number in takes fits, the player takes everything that is left. The game ends when the row is empty.

Both explorers play perfectly: each one always makes the choices that leave them with the best possible difference between their own score and their rival's.

Return Ada's final score minus Ben's final score.

Examples

Example 1

Input: prizes = [3, 9, 1, 2], takes = [1, 2]

Output: 9

Ada takes the first two chests (12). Ben is left with 1 and 2 and takes both (3). The margin is 12 - 3 = 9.

Example 2

Input: prizes = [4, -6, 5], takes = [2]

Output: -7

Ada must take two chests, 4 and -6, so she scores -2. One chest is left and 2 does not fit, so Ben takes it and scores 5. The margin is -2 - 5 = -7.

Example 3

Input: prizes = [7], takes = [2, 3]

Output: 7

Neither 2 nor 3 fits one chest, so Ada takes the whole row.

Constraints