Score | |
---|---|
Problem A | 460 |
Problem B | 690 |
Problem C | 1150 |
Problem D | 1380 |
Problem E | 1840 |
Problem F1 | 1380 |
Problem F2 | 920 |
Successful hack | 100 |
Unsuccessful hack | -50 |
Unsuccessful submission | -50 |
Resubmission | -50 |
This is the hard version of the problem. The difference is the constraints on
Alice and Bob are given the numbers
The game has a score that Alice tries to maximize, and Bob tries to minimize. The score is initially
Bob gets to know which number Alice picked before deciding whether to add or subtract the number from the score, and Alice gets to know whether Bob added or subtracted the number for the previous turn before picking the number for the current turn (except on the first turn since there was no previous turn).
If Alice and Bob play optimally, what will the final score of the game be?
The first line of the input contains a single integer
Each test case consists of a single line containing the three integers,
It is guaranteed that the sum of
For each test case output a single integer number — the score of the optimal game modulo
Formally, let
7 3 3 2 2 1 10 6 3 10 6 4 10 100 1 1 4 4 0 69 4 20
6 5 375000012 500000026 958557139 0 49735962
In the first test case, the entire game has
In the third test case, Alice has a strategy to guarantee a score of
In the fourth test case, Alice has a strategy to guarantee a score of
Name | |||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
No items |