/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君はお菓子屋さんで働いています。店には N 個のお菓子が左から右へ一列に並んでおり、左から i 番目（1 \leq i \leq N）のお菓子には「おいしさ」 A_i が定められています。
高橋君はこれからちょうど M 個の詰め合わせセットを作ります。各セットは、一列に並んだお菓子の中から連続する区間を 1 つ選んで構成します。具体的には、整数の組 (l, r)（1 \leq l \leq r \leq N）を 1 つ選び、番号 l, l+1, \ldots, r のお菓子をひとまとめにします。ただし、各区間の長さ r - l + 1 は K 以下でなければなりません。
M 個のセットを作る際、選ぶ M 個の区間はすべて異なっていなければなりません。すなわち、どの 2 つのセットについても、対応する組 (l, r) が一致してはいけません。一方で、異なるセットの区間同士が重なること、すなわち同じお菓子が複数のセットに含まれることは許されます。
各セットの「満足度」は、そのセットに含まれるお菓子のおいしさの総和として定義されます。すなわち、区間 (l, r) を選んだセットの満足度は A_l + A_{l+1} + \cdots + A_r です。
ちょうど M 個のセットを作るすべての方法のうち、M 個のセットの満足度の合計値の最大値を求め、出力してください。
なお、長さ K 以下の区間 (l, r) の総数は M 以上であることが保証されるため、条件を満たす M 個の異なる区間を選ぶことは常に可能です。
制約
- 1 \leq N \leq 3000
- 1 \leq K \leq N
- 1 \leq M \leq \displaystyle\sum_{k=1}^{K} (N - k + 1)（右辺は長さ K 以下の区間の総数に等しい）
- -10^6 \leq A_i \leq 10^6（1 \leq i \leq N）
- 入力はすべて整数である。
入力
N M K A_1 A_2 \ldots A_N
- 1 行目には、お菓子の個数を表す整数 N、作るセットの個数を表す整数 M、1 つのセットに含められるお菓子の個数の上限を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各お菓子のおいしさを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
M 個のセットの満足度の合計値の最大値を 1 行で出力せよ。
入力例 1
5 3 2 3 -1 4 1 5
出力例 1
16
入力例 2
7 5 3 2 -3 5 -1 8 -2 4
出力例 2
43
入力例 3
10 4 4 1 -2 3 4 -5 6 7 -8 9 1
出力例 3
49
Score : 333 pts
Problem Statement
Takahashi works at a candy shop. The shop has N candies lined up in a row from left to right, and the i-th candy from the left (1 \leq i \leq N) has a "deliciousness" value of A_i.
Takahashi will now make exactly M assortment sets. Each set is constructed by choosing one contiguous interval from the row of candies. Specifically, he chooses a pair of integers (l, r) (1 \leq l \leq r \leq N) and bundles together the candies numbered l, l+1, \ldots, r. However, the length r - l + 1 of each interval must be at most K.
When making the M sets, all M chosen intervals must be distinct. That is, for any two sets, their corresponding pairs (l, r) must not be identical. On the other hand, intervals of different sets are allowed to overlap, meaning the same candy may be included in multiple sets.
The "satisfaction" of each set is defined as the sum of deliciousness values of the candies included in that set. That is, the satisfaction of a set with interval (l, r) is A_l + A_{l+1} + \cdots + A_r.
Among all ways to make exactly M sets, find and output the maximum possible total satisfaction of the M sets.
It is guaranteed that the total number of intervals (l, r) with length at most K is at least M, so it is always possible to choose M distinct intervals satisfying the conditions.
Constraints
- 1 \leq N \leq 3000
- 1 \leq K \leq N
- 1 \leq M \leq \displaystyle\sum_{k=1}^{K} (N - k + 1) (the right-hand side equals the total number of intervals with length at most K)
- -10^6 \leq A_i \leq 10^6 (1 \leq i \leq N)
- All input values are integers.
Input
N M K A_1 A_2 \ldots A_N
- The first line contains the integer N representing the number of candies, the integer M representing the number of sets to make, and the integer K representing the upper limit on the number of candies that can be included in one set, separated by spaces.
- The second line contains the integers A_1, A_2, \ldots, A_N representing the deliciousness of each candy, separated by spaces.
Output
Output the maximum possible total satisfaction of the M sets in a single line.
Sample Input 1
5 3 2 3 -1 4 1 5
Sample Output 1
16
Sample Input 2
7 5 3 2 -3 5 -1 8 -2 4
Sample Output 2
43
Sample Input 3
10 4 4 1 -2 3 4 -5 6 7 -8 9 1
Sample Output 3
49