No.2835 Take and Flip
タグ : / 解いたユーザー数 194
作問者 :
milkcoffee
/ テスター :
first_vil
ygussany
Problem Statement
There are $N$ integers. The $i$-th integer is $A_i$. $\mathrm{First}$ and $\mathrm{Second}$ take turns performing the following operation, $1$ time per turn.
- Choose $1$ integer and delete it. Then, multiply all the remaining integers by $-1$.
$\mathrm{First}$ moves first, and the game ends when all the integers have been deleted.
Let $X$ be the sum of the integers deleted by $\mathrm{First}$, and $Y$ be the sum of the integers deleted by $\mathrm{Second}$. $\mathrm{First}$ wants to maximize $X-Y$, while $\mathrm{Second}$ wants to minimize $X-Y$.
Find the final value of $X-Y$ when both players play optimally.
Input
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
- $1 \leq N \leq 2 \times 10^5$
- $|A_i| \leq 10^9$ $(1 \leq i \leq N)$
- All input values are integers.
Output
Output the final value of $X-Y$ when both players play optimally, as an integer.
Sample
Sample 1
Input
3 -1 4 -2
Output
1
First, $\mathrm{First}$ chooses and deletes $4$, then multiplies the remaining integers by $-1$. The remaining integers become $1,2$.
Next, $\mathrm{Second}$ chooses and deletes $2$, then multiplies the remaining integers by $-1$. The remaining integer is $-1$.
Finally, $\mathrm{First}$ chooses and deletes $-1$. No integers remain.
Since $X=4 + (-1) = 3$ , $Y=2$, we have $X-Y = 1$.
Sample 2
Input
14 -523328364 -409607197 -712671537 -766381325 472867409 -811025573 -971818355 -66399298 633965694 -22544287 -720923839 -905888279 514666353 -359356404
Output
-4648445002
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。