/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は川を渡るための石渡りゲームに挑戦しています。
川には N 個の石が一列に並んでおり、左から順に石 1、石 2、…、石 N と番号が付けられています。石 i（1 \leq i \leq N）の上には A_i 枚のコインが置かれています。
高橋君は最初、石 1 の上に立っています。高橋君は石の上に立ったとき、その石の上にあるコインをすべて獲得します（最初に立っている石 1 のコインも獲得します）。立ち寄らなかった石のコインは獲得できません。コインの枚数は正とは限らず、負であることもあり、その場合も強制的に獲得します。
高橋君はまだ石 N に到達していない間、現在いる石から右方向に跳んで移動します。現在石 i（i < N）にいるとき、1 以上 K 以下の整数 d を選んで、石 i+d に移動することができます。ただし、移動先の石の番号は N 以下でなければなりません。すなわち、石 i+1, 石 i+2, \ldots, 石 \min(i+K,\, N) のいずれかに跳ぶことができます。移動は常に右方向であるため、同じ石に二度立つことはありません。
高橋君は必ず石 N に到達しなければなりません。石 N に到達し、そのコインを獲得した時点でゲームは終了します。制約より K \geq 1 であるため、石 1 から 1 歩ずつ進むことで必ず石 N に到達できます。
石 1 から出発し石 N に到達するまでに獲得できるコインの枚数の合計の最大値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N - 1
- -10^9 \leq A_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、石の個数を表す整数 N と、一度のジャンプで進める石の番号の差の最大値を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各石の上に置かれているコインの枚数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
石 1 から石 N まで移動するときに獲得できるコインの枚数の合計の最大値を 1 行で出力せよ。
Score : 466 pts
Problem Statement
Takahashi is attempting a stone jumping game to cross a river.
There are N stones lined up in a row in the river, numbered stone 1, stone 2, …, stone N from left to right. On stone i (1 \leq i \leq N), there are A_i coins placed.
Takahashi initially stands on stone 1. When Takahashi stands on a stone, he collects all the coins on that stone (including the coins on stone 1 where he starts). Coins on stones he does not visit cannot be collected. The number of coins is not necessarily positive; it can be negative, in which case he is forced to collect them as well.
While Takahashi has not yet reached stone N, he jumps to the right from his current stone. When he is currently on stone i (i < N), he can choose an integer d with 1 \leq d \leq K and move to stone i+d. However, the destination stone's number must be at most N. That is, he can jump to any one of stone i+1, stone i+2, \ldots, stone \min(i+K,\, N). Since movement is always to the right, he never stands on the same stone twice.
Takahashi must reach stone N. The game ends when he reaches stone N and collects its coins. Since K \geq 1 by the constraints, he can always reach stone N by advancing one step at a time from stone 1.
Find the maximum total number of coins Takahashi can collect starting from stone 1 and reaching stone N.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N - 1
- -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of stones and an integer K representing the maximum difference in stone numbers that can be covered in a single jump, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the number of coins placed on each stone, separated by spaces.
Output
Print in one line the maximum total number of coins that can be collected when moving from stone 1 to stone N.