/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、 N 個のブロックが一列に並んでいるパズルゲームをプレイしています。
左から i 番目のブロックには整数 A_i が書かれています。この値は正の場合も負の場合もあります。
高橋君は以下の操作を好きな回数（ 0 回以上）行うことができます。
操作: 連続する K 個のブロックを選び、それらをすべて消去する。消去されたブロックは消滅し、残ったブロックは左に詰められて再び一列に並びます。
高橋君は、最終的に残るブロックに書かれた整数の合計を最大化したいと考えています。
ただし、ブロックが 1 個も残らない場合、合計は 0 とします。
操作を最適に行ったとき、残るブロックに書かれた整数の合計の最大値を求めてください。
制約
- 1 \leq K \leq N \leq 10^6
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、ブロックの個数を表す N と、一度の操作で消去するブロックの個数を表す K が、スペース区切りで与えられる。
- 2 行目には、各ブロックに書かれた整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
残るブロックに書かれた整数の合計の最大値を 1 行で出力せよ。
入力例 1
5 2 3 -5 4 -2 1
出力例 1
4
入力例 2
6 3 -1 2 -3 4 -5 6
出力例 2
7
入力例 3
15 4 8 -10 3 5 -2 -7 6 1 -4 9 -8 2 7 -6 4
出力例 3
21
入力例 4
30 5 12 -5 -20 7 3 -8 15 -2 6 -11 4 9 -30 18 -1 5 -6 14 -9 2 -3 10 -12 8 1 -7 16 -4 -15 11
出力例 4
74
入力例 5
1 1 -1000000000
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi is playing a puzzle game where N blocks are arranged in a row.
The i-th block from the left has an integer A_i written on it. This value can be positive or negative.
Takahashi can perform the following operation any number of times (zero or more times).
Operation: Choose K consecutive blocks and remove all of them. The removed blocks disappear, and the remaining blocks are shifted to the left to form a single row again.
Takahashi wants to maximize the sum of the integers written on the blocks that remain in the end.
If no blocks remain, the sum is defined to be 0.
Find the maximum possible sum of the integers written on the remaining blocks when the operations are performed optimally.
Constraints
- 1 \leq K \leq N \leq 10^6
- -10^9 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains N, the number of blocks, and K, the number of blocks removed in a single operation, separated by a space.
- The second line contains the integers A_1, A_2, \ldots, A_N written on each block, separated by spaces.
Output
Print the maximum possible sum of the integers written on the remaining blocks in one line.
Sample Input 1
5 2 3 -5 4 -2 1
Sample Output 1
4
Sample Input 2
6 3 -1 2 -3 4 -5 6
Sample Output 2
7
Sample Input 3
15 4 8 -10 3 5 -2 -7 6 1 -4 9 -8 2 7 -6 4
Sample Output 3
21
Sample Input 4
30 5 12 -5 -20 7 3 -8 15 -2 6 -11 4 9 -30 18 -1 5 -6 14 -9 2 -3 10 -12 8 1 -7 16 -4 -15 11
Sample Output 4
74
Sample Input 5
1 1 -1000000000
Sample Output 5
0