#PQJ1878x9913. QOJ 1878_9913
QOJ 1878_9913
第三试绝顶之战(struggle) IOI2025 中国国家集训队集中培训 绝顶之战(struggle) 【题目描述】 有一个长度为m 的一维空间,还有n 个物品,第i 个物品的长度为ai。现在按照 编号从小到大的顺序依次将物品放入空间中,对于第i 个物品: • 如果当前空间中存在一段连续的长度至少为ai 的空余,则你.必.须将第i 个物品 放入一段连续的长度为ai 的空余空间中。 • 否则,第i 个物品无法被放入,跳过它。 你需要输出:按照编号从小到大的顺序考虑完所有物品后,所有可能的.空.间.占.用.长 .度,它的定义是所有被放入空间的物品的长度之和。 【输入格式】 从标准输入读入数据。 输入的第一行两个整数m, n,分别表示空间长度和物品个数。 第二行n 个整数a1, · · · , an,依次表示每个物品的长度。 【输出格式】 输出到标准输出。 输出两行,第一行一个整数S,表示可能的空间占用长度的数量。 第二行S 个整数b1, . . . , bS,.从.小.到.大输出所有可能的空间占用长度。 注意,你需要保证b1, . . . , bS 不重不漏。 【样例1 输入】 8 4 1 3 4 1 2 2 【样例1 输出】 4 1 4 6 7 8 2 【样例1 解释】 下图分别展示了空间占用长度为4, 6, 7, 8 的一种可能方式: 第4 页 共8 页 第三试绝顶之战(struggle) IOI2025 中国国家集训队集中培训 图1: 样例解释1 【样例2】 见题目目录下的2.in 与2.ans。 【子任务】 对于所有测试数据,1 ≤m, ai ≤1016,1 ≤n ≤14。 子任务编号 分数 m, ai ≤ n = Subtask 1 5 10 15 Subtask 2 2 Subtask 3 3 Subtask 4 5 5 Subtask 5 7 Subtask 6 1016 9 Subtask 7 11 Subtask 8 12 10 Subtask 9 13 Subtask 10 14 30 第5 页 共8 页