/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 人の選手を 2 つのチームに分けて綱引きの試合を行おうとしています。i 番目の選手の力は A_i です。
N 人の選手それぞれをチーム 1 またはチーム 2 のいずれかに割り当てます。すべての選手はちょうど一方のチームに属さなければなりません。ただし、一方のチームの人数が 0 人であっても構いません。
チーム 1 に属する選手の力の合計を S_1、チーム 2 に属する選手の力の合計を S_2 とします。S_1 + S_2 は全選手の力の総和で一定なので、\min(S_1, S_2) を最大化することは |S_1 - S_2| を最小化することと同値です。試合をできるだけ拮抗させるために、\min(S_1, S_2) の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^4
- 1 \leq A_i \leq 2 \times 10^5 \quad (1 \leq i \leq N)
- \displaystyle \sum_{i=1}^{N} A_i \leq 2 \times 10^5
- 入力はすべて整数である
入力
N A_1 A_2 : A_N
- 1 行目には、選手の人数を表す整数 N が与えられる。
- 続く N 行のうち i 行目には、i 番目の選手の力を表す整数 A_i が与えられる。
出力
\min(S_1, S_2) の最大値を整数で 1 行に出力してください。
入力例 1
4 1 2 3 4
出力例 1
5
入力例 2
3 2 5 8
出力例 2
7
入力例 3
12 13 7 11 2 9 4 8 6 5 10 3 12
出力例 3
45
入力例 4
20 12000 11500 11000 10500 10000 9500 9000 8500 8000 7500 7000 6500 6000 5500 5000 4500 4000 3500 3000 2500
出力例 4
72500
入力例 5
1 200000
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi wants to divide N players into 2 teams to hold a tug-of-war match. The strength of the i-th player is A_i.
Each of the N players is assigned to either Team 1 or Team 2. Every player must belong to exactly one team. However, it is allowed for one of the teams to have 0 members.
Let S_1 be the total strength of the players belonging to Team 1, and S_2 be the total strength of the players belonging to Team 2. Since S_1 + S_2 is constant (the total strength of all players), maximizing \min(S_1, S_2) is equivalent to minimizing |S_1 - S_2|. To make the match as competitive as possible, find the maximum value of \min(S_1, S_2).
Constraints
- 1 \leq N \leq 2 \times 10^4
- 1 \leq A_i \leq 2 \times 10^5 \quad (1 \leq i \leq N)
- \displaystyle \sum_{i=1}^{N} A_i \leq 2 \times 10^5
- All inputs are integers
Input
N A_1 A_2 : A_N
- The first line contains an integer N representing the number of players.
- The i-th of the following N lines contains an integer A_i representing the strength of the i-th player.
Output
Output the maximum value of \min(S_1, S_2) as an integer on a single line.
Sample Input 1
4 1 2 3 4
Sample Output 1
5
Sample Input 2
3 2 5 8
Sample Output 2
7
Sample Input 3
12 13 7 11 2 9 4 8 6 5 10 3 12
Sample Output 3
45
Sample Input 4
20 12000 11500 11000 10500 10000 9500 9000 8500 8000 7500 7000 6500 6000 5500 5000 4500 4000 3500 3000 2500
Sample Output 4
72500
Sample Input 5
1 200000
Sample Output 5
0