/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
キーエンス本社に勤務する人数が増えてきたので、本社に存在する部署を 2 つのグループに分け、昼休みの時間帯を分けることにしました。
キーエンス本社には N 個の部署が存在し、i 番目 (1\leq i\leq N) の部署に所属する人数は K_i 人です。
それぞれの部署をグループ A, B のいずれか一方に割り当て、グループごとに同時に昼休みをとり、
かつグループ A, B の昼休みの時間が重ならないようにしたとき、同時に昼休みをとる最大人数としてあり得る最小の値を求めてください。
すなわち、グループ A に割り当てられた部署に所属する人数の合計とグループ B に割り当てられた部署に所属する人数の合計
のうち大きい方の値としてあり得る最小の値を求めてください。
制約
- 2\leq N \leq 20
- 1\leq K_i \leq 10^8
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K_1 K_2 \ldots K_N
出力
同時に昼休みを取る最大人数としてあり得る最小の値を出力せよ。
入力例 1
5 2 3 5 10 12
出力例 1
17
1,2,5 番目の部署をグループ A に、3,4 番目の部署をグループ B に割り当てたとき、 グループ A に割り当てられた部署に所属する人数の合計は 2+3+12=17 、 グループ B に割り当てられた部署に所属する人数の合計は 5+10=15 となり、 このとき同時に昼休みを取る最大人数は 17 となります。
一方で、グループ A,B それぞれに割り当てられた部署に所属する人数の合計がいずれも 16 以下になるように 部署を割り当てることはできないため、17 を出力します。
入力例 2
2 1 1
出力例 2
1
同一人数の部署が複数存在する可能性もあります。
入力例 3
6 22 25 26 45 22 31
出力例 3
89
例えば、1,4,5 番目の部署をグループ A に、2,3,6 番目の部署をグループ B に割り当てたとき同時に昼休みを取る最大人数は 89 となります。
Score : 300 points
Problem Statement
As KEYENCE headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.
KEYENCE headquarters have N departments, and the number of people in the i-th department (1\leq i\leq N) is K_i.
When assigning each department to Group A or Group B, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group A and Group B do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group A, and the total number of people in departments assigned to Group B.
Constraints
- 2 \leq N \leq 20
- 1 \leq K_i \leq 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K_1 K_2 \ldots K_N
Output
Print the minimum possible value of the maximum number of people taking a lunch break at the same time.
Sample Input 1
5 2 3 5 10 12
Sample Output 1
17
When assigning departments 1, 2, and 5 to Group A, and departments 3 and 4 to Group B, Group A has a total of 2+3+12=17 people, and Group B has a total of 5+10=15 people. Thus, the maximum number of people taking a lunch break at the same time is 17.
It is impossible to assign the departments so that both groups have 16 or fewer people, so print 17.
Sample Input 2
2 1 1
Sample Output 2
1
Multiple departments may have the same number of people.
Sample Input 3
6 22 25 26 45 22 31
Sample Output 3
89
For example, when assigning departments 1, 4, and 5 to Group A, and departments 2, 3, and 6 to Group B, the maximum number of people taking a lunch break at the same time is 89.