No.2835 Take and Flip
タグ : / 解いたユーザー数 176
作問者 :
milkcoffee
/ テスター :
first_vil
ygussany
問題文
$N$ 個の整数があります。$i$ 番目の整数は $A_i$ です。$\mathrm{First}$ 君と $\mathrm{Second}$ 君が交互に $1$ 回ずつ以下の操作を行います。
- 整数を $1$ つ選び、それを削除する。その後、残っている整数を全て $-1$ 倍する。
$\mathrm{First}$ 君が先手で、整数が全て削除されたら終了します。
$\mathrm{First}$ 君が削除した整数の和を $X$ 、 $\mathrm{Second}$ 君が削除した整数の和を $Y$ とします。$\mathrm{First}$ 君は $X-Y$ を最大化したいですが、 $\mathrm{Second}$ 君は $X-Y$ を最小化したいです。
両者が最善を尽くしたときの最終的な $X-Y$ を求めてください。
入力
$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)$
- 入力は全て整数
出力
両者が最善を尽くしたときの最終的な $X-Y$ を整数で出力してください。
サンプル
サンプル1
入力
3 -1 4 -2
出力
1
最初、 $\mathrm{First}$ 君が $4$ を選んで削除し、残りの整数を $-1$ 倍します。 残りの整数は $1,2$ になります。
次に、$\mathrm{Second}$ 君が $2$ を選んで削除し、残りの整数を $-1$ 倍します。 残りの整数は $-1$ です。
最後に、 $\mathrm{First}$ 君が $-1$ を選んで削除します。残りの整数はありません。
$X=4 + (-1) = 3$ , $Y=2$ であるため、 $X-Y = 1$ です。
サンプル2
入力
14 -523328364 -409607197 -712671537 -766381325 472867409 -811025573 -971818355 -66399298 633965694 -22544287 -720923839 -905888279 514666353 -359356404
出力
-4648445002
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。