/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
N 個のマスが横一列に並んでいて、左から i 番目のマスには整数 A_i が書かれています。
また、あなたは連続するマス K 個を覆えるタイルを \lfloor \frac{N}{K}\rfloor 枚持っています。
i=1,\ldots,\lfloor \frac{N}{K}\rfloor について以下の問題を解いてください。
- タイルを重ならずにちょうど i 個置くとき、タイルで覆われたマスに書かれた数の和としてありうる値の最大値を求めよ。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq K \leq \min(5,N)
- -10^9\leq A_i\leq 10^9
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 \ldots A_N
出力
i=1,\ldots,\lfloor \frac{N}{K}\rfloor に対する問題の答えを空白区切りで一行に出力せよ。
入力例 1
6 2 -5 3 4 -1 6 -2
出力例 1
7 12 5
i=1 の場合、左から 2 番目のマスと 3 番目のマスをタイル 1 枚で覆うと、覆われたマスに書かれた数の和は 7 となります。
i=2 の場合、左から 2 番目のマスと 3 番目のマスをタイル 1 枚で覆い、左から 4 番目のマスと 5 番目のマスをタイル 1 枚で覆うと、覆われたマスに書かれた数の和は 12 となります。
入力例 2
20 4 -5 3 4 -1 6 -2 13 -1 13 7 6 -12 3 -5 12 -6 -3 10 -15 -5
出力例 2
32 45 57 52 22
Score : 625 points
Problem Statement
You have a row of N cells. The i-th cell from the left contains an integer A_i.
You also have \lfloor \frac{N}{K} \rfloor tiles, each of which covers K consecutive cells.
For each i = 1, \ldots, \lfloor \frac{N}{K} \rfloor, solve the following problem:
- When placing exactly i tiles without overlap, find the maximum possible sum of the numbers in the covered cells.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min(5,N)
- -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 A_1 \ldots A_N
Output
Print the answers for i = 1, \ldots, \lfloor \frac{N}{K} \rfloor separated by spaces in one line.
Sample Input 1
6 2 -5 3 4 -1 6 -2
Sample Output 1
7 12 5
For i=1, if you cover the 2nd and 3rd cells with one tile, the sum of the numbers in the covered cells is 7.
For i=2, if you cover the 2nd and 3rd cells with one tile and the 4th and 5th cells with another tile, the sum of the numbers in the covered cells is 12.
Sample Input 2
20 4 -5 3 4 -1 6 -2 13 -1 13 7 6 -12 3 -5 12 -6 -3 10 -15 -5
Sample Output 2
32 45 57 52 22