All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef and his brother Chefu are playing a game. The game consist of two sequences of integers A of length N and B of length M, and it will last for exactly M turns, Chef will play in odd turns whereas Chefu will play in even turns (turns and sequences are 1-based).
In the i-th turn, the corresponding player should select an interval (continuous subsegment) of sequence A of length Bi that is strictly inside the interval selected in previous turn, i.e. if the interval in previous turn was [l,r] then if the interval in current turn is [u,v] then it should satisfy l < u ≤ v < r, except in the first turn where the player can select any interval of length B1.
Initially the score of the game is 0. If it was Chef's turn then we add to the score of the game points equal to sum of integers of the selected interval of sequence A. If it was Chefu's turn then we subtract from the score of the game points equal to sum of integers of the selected interval of sequence A.
Chef wants to maximize the score of the game in the end while Chefu want to minimize it. Can you find out the score of the game in the end given that both Chef and Chefu are playing optimally.
The first line contains an integer T denoting the number of test-cases. Description of T test cases follow.
First line of each test case contains two space separated integers N and M, denoting the length of the sequence and the number of turns for which the game will last, respectively.
Second line of each test case contains N space separated integers denoting the sequence A
Third line of each test case contains M space separated integers denoting the sequence B
For each test case, output a single integer in a separate line corresponding to the score of the game at the end of the game.
- 1 ≤ T ≤ 10,000
- 1 ≤ sum of N in all test-cases ≤ 300,000
- 1 ≤ Ai ≤ 1,000,000,000
- 1 ≤ M ≤ 200
- 1 ≤ Bi ≤ N
- For each valid i: Bi+1 + 2 ≤ Bi
- Subtask #1 (20 points): sum of N in all test-cases ≤ 400
- Subtask #2 (20 points): M = 2
- Subtask #3 (60 points: No additional constraints
Input: 1 8 3 3 7 5 4 9 6 1 3 6 3 1 Output: 20
Example case 1. Chef chooses the interval [1, 6] (i.e. (3, 7, 5, 4, 9, 6)). The score now is 34 points.
In the next turn, Chefu chooses the interval [3, 5] (i.e. (5, 4, 9)). The score now is 34 - 18 = 16 points.
In the next turn, Chef chooses the interval [4, 4] (i.e. (4)). So finally score of the game is 16 + 4 =20.
This is the score of the game when both Chef and Chefu play optimally.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.