← 返回题目列表

AtCoder · agc062_c

C. 子集和的 Mex

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

分数: 800 点

问题陈述

给你一个长度的整数序列 N: A=(A_1,A_2,\dots,A_N).

找到 K 最小正整数 X 满足以下条件。

  • 有 no 的非空(不一定连续)子序列 A 其元素总和为 X.

约束

  • 1 \leq N \leq 60
  • 1 \leq K \leq 1000
  • 1 \leq A_i \leq 10^{15}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \dots A_N

输出

打印 K 满足条件的最小正整数按升序排列,以空格分隔。


示例输入 1

3 3
1 2 5

示例输出 1

4 9 10

的子序列 A 是 (1),(2),(1,2),(5),(1,5),(2,5),(1,2,5),它们各自的总和是 1,2,3,5,6,7,8。因此,对于 X=1,2,3,5,6,7,8,有以下子序列 A 其元素总和为 X.

另一方面,对于 X=4,9,10,没有子序列 A 其元素总和为 X.


示例输入 2

20 10
324 60 1 15 60 15 1 60 319 1 327 1 2 60 2 345 1 2 2 15

示例输出 2

14 29 44 59 74 89 104 119 134 149