/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
以下の条件を満たす正整数 X を小さいほうから順に K 個求めてください。
- 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 に対しては、要素の和が X であるような A の部分列が存在します。
一方 X=4,9,10 に対しては、要素の和が X であるような A の部分列は存在しません。
入力例 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
Score : 800 points
Problem Statement
You are given an integer sequence of length N: A=(A_1,A_2,\dots,A_N).
Find the K smallest positive integers X that satisfy the following condition.
- There is no non-empty (not necessarily contiguous) subsequence of A whose elements sum to X.
Constraints
- 1 \leq N \leq 60
- 1 \leq K \leq 1000
- 1 \leq A_i \leq 10^{15}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the K smallest positive integers satisfying the conditions in ascending order, separated by spaces.
Sample Input 1
3 3 1 2 5
Sample Output 1
4 9 10
The subsequences of A are (1),(2),(1,2),(5),(1,5),(2,5),(1,2,5), and their respective sums are 1,2,3,5,6,7,8. Therefore, for X=1,2,3,5,6,7,8, there are subsequences of A whose elements sum to X.
On the other hand, for X=4,9,10, there is no subsequence of A whose elements sum to X.
Sample Input 2
20 10 324 60 1 15 60 15 1 60 319 1 327 1 2 60 2 345 1 2 2 15
Sample Output 2
14 29 44 59 74 89 104 119 134 149