/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は庭園にある石畳の小道を歩いています。小道には N 個の飛び石が一列に並んでおり、左から順に 1, 2, \ldots, N と番号が付けられています。各飛び石 i には景観の評価を表すスコア A_i が設定されています。スコアは負の値をとることもあります。
高橋君は飛び石 1 からスタートし、飛び石 N まで移動します。現在飛び石 i にいるとき、次のいずれかの行動を取ることができます：
- 一歩進む：飛び石 i + 1 に移動する（i + 1 \leq N の場合のみ）。
- 一つ飛ばしで跳ぶ：飛び石 i + 1 を飛び越え、そこには立ち寄らずに飛び石 i + 2 に移動する（i + 2 \leq N の場合のみ）。
「一つ飛ばしで跳ぶ」動作は体力を消耗するため、飛び石 1 から飛び石 N までの移動を通して最大 K 回までしか行えません（0 回でも構いません）。「一歩進む」動作の回数に制限はありません。
高橋君は飛び石 N に到達した時点で移動を終了します。移動の過程で高橋君が訪れた飛び石すべて（出発地点の飛び石 1 および到達地点の飛び石 N を含む）のスコアの合計を最大化してください。その最大値を求めてください。
なお、「一つ飛ばしで跳ぶ」動作を一切使わず、すべて「一歩進む」で移動すれば必ず飛び石 N に到達できるため、条件を満たす移動方法は常に存在します。
制約
- 2 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- -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 から飛び石 N まで移動するとき、訪れた飛び石のスコアの合計の最大値を 1 行で出力せよ。
入力例 1
5 1 3 -5 4 -2 6
出力例 1
11
入力例 2
4 0 -1 2 -3 4
出力例 2
2
入力例 3
12 3 5 -10 8 -3 7 -20 4 6 -2 9 -15 10
出力例 3
44
入力例 4
30 10 12 -5 7 -100 20 3 -8 15 -30 6 9 -2 -50 25 4 -1 18 -40 11 13 -7 5 -60 30 2 -3 16 -20 8 10
出力例 4
211
入力例 5
2 2 -1000000000 -1000000000
出力例 5
-2000000000
Score : 433 pts
Problem Statement
Takahashi is walking along a stone-paved path in a garden. The path has N stepping stones arranged in a row, numbered 1, 2, \ldots, N from left to right. Each stepping stone i has a score A_i representing its scenic evaluation. Scores can be negative.
Takahashi starts at stepping stone 1 and moves to stepping stone N. When currently on stepping stone i, he can take one of the following actions:
- Step forward: Move to stepping stone i + 1 (only if i + 1 \leq N).
- Skip one stone: Jump over stepping stone i + 1 without visiting it, and move to stepping stone i + 2 (only if i + 2 \leq N).
Since the "skip one stone" action is physically exhausting, it can be performed at most K times throughout the entire journey from stepping stone 1 to stepping stone N (it is also fine to use it 0 times). There is no limit on the number of "step forward" actions.
Takahashi ends his journey upon reaching stepping stone N. Maximize the total score of all stepping stones that Takahashi visits during his journey (including the starting stone 1 and the destination stone N). Find this maximum value.
Note that by using only "step forward" actions without any "skip one stone" actions, Takahashi can always reach stepping stone N, so a valid way of moving always exists.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of stepping stones and an integer K representing the maximum number of "skip one stone" actions, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the scores of each stepping stone, separated by spaces.
Output
Print in one line the maximum total score of the stepping stones visited when Takahashi moves from stepping stone 1 to stepping stone N.
Sample Input 1
5 1 3 -5 4 -2 6
Sample Output 1
11
Sample Input 2
4 0 -1 2 -3 4
Sample Output 2
2
Sample Input 3
12 3 5 -10 8 -3 7 -20 4 6 -2 9 -15 10
Sample Output 3
44
Sample Input 4
30 10 12 -5 7 -100 20 3 -8 15 -30 6 9 -2 -50 25 4 -1 18 -40 11 13 -7 5 -60 30 2 -3 16 -20 8 10
Sample Output 4
211
Sample Input 5
2 2 -1000000000 -1000000000
Sample Output 5
-2000000000