← 返回题目列表

AtCoder · abc440_e

E. 饼干

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

分数: 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