B - カードの取り合い 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君と青木君が、N 枚のカードを使ったゲームをします。

各カードには点数が書かれており、i 番目 (1 \leq i \leq N) のカードの点数は A_i です。

高橋君を先手として、二人は交互に以下の操作を行います。

  • 残っているカードの中から好きな 1 枚を選び、自分のものとする。

すべてのカードが取られたとき、ゲームは終了します。高橋君は自分が取ったカードの点数の合計を最大化したいと考え、青木君は高橋君が取ったカードの点数の合計を最小化したいと考えています。

両者が最適に行動したとき、高橋君が取ったカードの点数の合計を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、カードの枚数を表す整数 N が与えられる。
  • 2 行目には、各カードの点数を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

両者が最適に行動したときの、高橋君が取ったカードの点数の合計を 1 行で出力せよ。

入力例 1

3
2 7 4

出力例 1

9

入力例 2

5
8 8 3 3 8

出力例 2

19

入力例 3

8
12 45 7 30 18 60 25 11

出力例 3

119

入力例 4

16
100 3 250 17 89 400 56 230 91 12 345 678 54 321 222 150

出力例 4

1750

入力例 5

1
1000000000

出力例 5

1000000000

Score : 300 pts

Problem Statement

Takahashi and Aoki play a game using N cards.

Each card has a score written on it, and the score of the i-th card (1 \leq i \leq N) is A_i.

With Takahashi going first, the two players alternately perform the following operation:

  • Choose any 1 card from the remaining cards and take it for yourself.

The game ends when all cards have been taken. Takahashi wants to maximize the total score of the cards he has taken, while Aoki wants to minimize the total score of the cards Takahashi has taken.

Find the total score of the cards Takahashi has taken when both players play optimally.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of cards.
  • The second line contains N integers A_1, A_2, \ldots, A_N representing the scores of each card, separated by spaces.

Output

Print on one line the total score of the cards Takahashi has taken when both players play optimally.

Sample Input 1

3
2 7 4

Sample Output 1

9

Sample Input 2

5
8 8 3 3 8

Sample Output 2

19

Sample Input 3

8
12 45 7 30 18 60 25 11

Sample Output 3

119

Sample Input 4

16
100 3 250 17 89 400 56 230 91 12 345 678 54 321 222 150

Sample Output 4

1750

Sample Input 5

1
1000000000

Sample Output 5

1000000000