시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 5 | 1 | 1 | 33.333% |
Is it a notorious coincidence with this problem?
Cinderella and her wicked Stepmother are playing the game. Cinderella has $n$ non-negative integers \(a_1, a_2, \dots , a_n\) at first. There are two parameters $A$ and $B$
for this game.Cinderella and Stepmother take turns playing, starting with Cinderella. One each turn, Cinderella can replace the sequence \(a_1, a_2, \dots, a_n\) by a new integer sequence \(a'_1, a'_2, \dots , a'_n\) such that
Then Stepmother can choose $B$ indices $i_1, i_2, \dots , i_B$, and set $a_{i_1}, a_{i_2}, \dots , a_{i_B}$ to 0.
The game continues forever. Let $M$ be the maximum value of $a_1, a_2, \dots , a_n$ for all the time. Cinderella wants to maximize $M$, and Stepmother wants to minimize $M$.
Determine the value of $M$ if both players play optimally.
The first line contains an integer $T$ ($1 \le T \le 10^5$) indicating the number of test cases. For each test case:
The first line contains three integers $n, A, B$ ($1 \le B \le n \le 10^5, 0 \le A \le 10^{12}$).
The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($0 \le a_i \le 10^{12}$).
It is guaranteed that \(\sum{n} \le 5 \times 10^5\).
For each test case, output a line containing one integer: the answer.
4 3 5 1 1 2 3 5 5 1 0 2 1 0 3 5 100 5 1 2 3 4 5 8 3 1 5 1 2 2 0 2 5 1
11 14 105 9
A possible game process for the first test case:
{1, 2, 3} → {3, 4, 4} → {3, 4, 0} → {6, 6, 0} → {6, 0, 0} → {11, 0, 0}.