子集和的中位数(Median of Subset Sums)

题目描述

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$，这些数可以组成 $2^n-1$ 个集合（不算空集）。由于 $a_i$ 可能重复，为方便起见，规定它们组成的集合中允许出现重复的元素。

分别计算每个集合的元素之和，请从中找到这些和的中位数。中位数是指排序后名次恰好在中间的数。

例如对于 $2,3,3$ 来说，可以组成的子集有

$$\{2\}, \{3\}, \{3\}, \{2,3\}, \{2,3\}, \{3,3\}, \{2,3,3\}$$

它们的和分别为

$$2, 3, 3, 5, 5, 6, 8$$

中位数是 $5$。

输入格式

第一行：单个整数 $n$；

第二行：$n$ 个整数 $a_1,\dots,a_n$。

输出格式

单个整数：表示这些集合之和的中位数。

样例输入 #1

3
2 3 3

样例输出 #1

5

样例输入 #2

1
10

样例输出 #2

10

数据范围

• $1\le a_i\le 2500$；
• 对于 $20\%$ 的数据，$1\le n\le 10$；
• 对于 $40\%$ 的数据，$1\le n\le 20$；
• 对于 $70\%$ 的数据，$1\le n\le 500$；
• 对于 $100\%$ 的数据，$1\le n\le 1500$。

知识点与难度

本题涉及的知识点从属于 GESP 八级（动态规划、bitset 优化、数学证明），难度等级：⭐⭐⭐⭐。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1~2	样例
1	20	3~8	小规模 / 特殊性质
2	15	9~11	Hack
3	30	12~20	中大规模
4	25	21~25	随机回归