【清华集训2024】绝顶之战 - 题目

有一个长度为 $m$ 的一维空间，还有 $n$ 个物品，第 $i$ 个物品的长度为 $a_{i}$ 。现在按照编号从小到大的顺序依次将物品放入空间中，对于第 $i$ 个物品：

你需要输出：按照编号从小到大的顺序考虑完所有物品后，所有可能的空间占用长度，它的定义是所有被放入空间的物品的长度之和。

输入的第一行两个整数 $m, n$ ，分别表示空间长度和物品个数。

第二行 $n$ 个整数 $a_{1}, \dots, a_{n}$ ，依次表示每个物品的长度。

输出两行，第一行一个整数 $S$ ，表示可能的空间占用长度的数量。

第二行 $S$ 个整数 $b_{1}, \dots, b_{S}$ ，从小到大输出所有可能的空间占用长度。

注意，你需要保证 $b_{1}, \dots, b_{S}$ 不重不漏。

8 4
3 4 1 2

4
4 6 7 8

下图分别展示了空间占用长度为 $4, 6, 7, 8$ 的一种可能方式：

见题目目录下的 2.in 与 2.ans。

见题目目录下的 2.in 与 2.ans。

对于所有测试数据， $1 \leq m, a_{i} \leq 10^{16}$ ， $1 \leq n \leq 14$ 。

子任务编号	$n =$	$m, a_{i} \leq$	分数
$1$	$5$	$10$	$15$
$2$	$2$	$10^{16}$	$5$
$3$	$3$	$10^{16}$	$5$
$4$	$5$	$10^{16}$	$5$
$5$	$7$	$10^{16}$	$5$
$6$	$9$	$10^{16}$	$5$
$7$	$11$	$10^{16}$	$10$
$8$	$12$	$10^{16}$	$10$
$9$	$13$	$10^{16}$	$10$
$10$	$14$	$10^{16}$	$30$

时间限制： $1s$

空间限制： $512MB$

Universal Online Judge