分数: 450 点
问题陈述
有 10^{100} 每个 cookie N 类型。每块饼干的美味程度 i-th 类型是 A_i.
您总共将选择 K 来自这些的cookie。当且仅当所选 cookie 类型的多集匹配时,两种选择 cookie 的方式才被认为是相同的。
对于每个 \binom{N+K-1}{K} 选择方式,考虑所选饼干的美味程度总和。让 S_1,S_2,\dots 是按降序排列的这些总和,包括重复项。查找 S_1,\dots,S_X.
约束
- 1\leq N \leq 50
- 1 \leq K \leq 10^5
- 1 \leq X \leq \min\left(10^5, \binom{N+K-1}{K}\right)
- -10^9 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K X A_1 \dots A_N
输出
让 S_1,S_2,\dots 是所选择的美味程度的可能总和 K cookie 按降序排列,包括重复项。输出 S_1,\dots,S_X 按此顺序,用换行符分隔。
样本输入 1
2 4 3 20 10
示例输出 1
80 70 60
有 5 选择方式 4 饼干:“k 类型的 cookie 1 和 4-k 类型的 cookie 2" (0\leq k \leq 4),其中所选饼干的美味度总和是 80,70,60,50,40.
示例输入 2
3 100000 5 -1 -1 -1
示例输出 2
-100000 -100000 -100000 -100000 -100000
不同的选择饼干的方式可能会带来同样的美味。
示例输入 3
9 14142 13 31 41 59 26 53 58 97 93 23
示例输出 3
1371774 1371770 1371766 1371762 1371758 1371754 1371750 1371746 1371742 1371738 1371736 1371735 1371734