/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
N 種類のクッキーがそれぞれ 10^{100} 枚あります。 i 種類目のクッキーの 1 枚あたりの美味しさは A_i です。
これらのクッキーから合計で K 枚を選びます。クッキーの選び方は、選んだクッキーの種類の多重集合が一致するときかつその時に限り同じとみなします。
全ての選び方 \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
出力
K 枚選んだクッキーの美味しさの和として考えられる値を、大きなものから順に重複を込めて S_1,S_2,\dots とするとき、S_1,\dots,S_X をこの順に改行区切りで出力せよ。
入力例 1
2 4 3 20 10
出力例 1
80 70 60
クッキーを 4 枚選ぶ方法は、「 1 種類目を k 枚、 2 種類目を 4-k 枚」(0\leq k \leq 4) の 5 通りあり、選んだクッキーの美味しさの和はそれぞれ 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
Score : 450 points
Problem Statement
There are 10^{100} cookies of each of N types. The deliciousness per cookie of the i-th type is A_i.
You will choose a total of K cookies from these. Two ways of choosing cookies are considered the same if and only if the multisets of types of chosen cookies match.
For each of the \binom{N+K-1}{K} ways of choosing, consider the sum of deliciousness of the chosen cookies. Let S_1,S_2,\dots be these sums in descending order, with duplicates included. Find S_1,\dots,S_X.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K X A_1 \dots A_N
Output
Let S_1,S_2,\dots be the possible sums of deliciousness of the chosen K cookies in descending order, with duplicates included. Output S_1,\dots,S_X in this order, separated by newlines.
Sample Input 1
2 4 3 20 10
Sample Output 1
80 70 60
There are 5 ways to choose 4 cookies: "k cookies of type 1 and 4-k cookies of type 2" (0\leq k \leq 4), where the sums of deliciousness of the chosen cookies are 80,70,60,50,40.
Sample Input 2
3 100000 5 -1 -1 -1
Sample Output 2
-100000 -100000 -100000 -100000 -100000
Different ways of choosing cookies may result in the same sum of deliciousness.
Sample Input 3
9 14142 13 31 41 59 26 53 58 97 93 23
Sample Output 3
1371774 1371770 1371766 1371762 1371758 1371754 1371750 1371746 1371742 1371738 1371736 1371735 1371734