← 返回题目列表

AtCoder · abc374_c

E. 分开午餐

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

由于 KEYENCE 总部的员工越来越多,他们决定将总部各部门分成两组,并错开午休时间。

KEYENCE 总部有 N 部门,以及人员数量 i第部门 (1\leq i\leq N) is 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.

不可能分配部门以使两个组都有 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.