Separated Lunch

题目描述

随着 KEYENCE 总部的员工越来越多，他们决定将总部的部门分为两组并错开午休时间。 KEYENCE 总部有 $N$ 个部门，第 $i$ 个部门 $(1\leq i\leq N)$ 的人数为 $K_i$。 在将每个部门分配到 A 组或 B 组，使得每组同时午休且 A 组与 B 组的午休时间不重叠的前提下，求同时午休人数的最大值的最小可能值。
换句话说，求下列两者中的较大值（被分配到 A 组的部门人数总和，和被分配到 B 组的部门人数总和）的最小可能值。

输入格式

输入按下列格式从标准输入给出： $N$ $K_1$ $K_2$ $\ldots$ $K_N$

输出格式

输出同时午休人数的最大值的最小可能值。

5
2 3 5 10 12

17

2
1 1

1

6
22 25 26 45 22 31

89

提示

$2 \leq N \leq 20$ $1 \leq K_i \leq 10^8$ 所有输入值均为整数。当将部门 $1$、$2$、$5$ 分配到 A 组，将部门 $3$、$4$ 分配到 B 组时，A 组共有 $2+3+12=17$ 人，B 组共有 $5+10=15$ 人。因此，同时午休人数的最大值为 $17$。 不可能将部门分配为使得两组的人数都不超过 $16$，所以输出 $17$。
多个部门可能具有相同的人数。
例如，当将部门 $1$、$4$、$5$ 分配到 A 组，将部门 $2$、$3$、$6$ 分配到 B 组时，同时午休人数的最大值为 $89$。

标签: AtCoder|abc374C

来源

AtCoder|abc374C