E - Minimum Cost of Stepping Stones Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は川を渡ろうとしています。川には一列に N 個の飛び石が並んでおり、左岸側から順に石 1, 石 2, \ldots, 石 N と番号が付けられています。高橋君は石 1 からスタートし、石 N に到達すればゴールです。

高橋君は現在いる石 i から、石 i+1, 石 i+2, \ldots, 石 \min(i+K,\, N) のいずれか 1 つへジャンプすることができます。つまり、一度のジャンプで進める石の番号の差は 1 以上 K 以下であり、必ず番号が増える方向にしか進めません。高橋君は最終的に石 N にちょうど着地しなければなりません。

各飛び石 i (1 \leq i \leq N) には正の整数値 A_i が設定されています。高橋君がある石に着地すると、その石の値が累計コストに加算されます。着地しなかった石の値は加算されません。スタート地点である石 1 の値 A_1 と、ゴール地点である石 N の値 A_N も、それぞれ着地時に加算されます。

高橋君が石 1 から石 N まで渡る経路のうち、累計コストが最小となるものを求め、その最小の累計コストを出力してください。

制約

  • 2 \leq N \leq 10^6
  • 1 \leq K \leq N - 1
  • 1 \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 行で出力せよ。

入力例 1

5 2
1 3 2 4 1

出力例 1

4

入力例 2

6 3
10 1 1 1 1 10

出力例 2

21

入力例 3

10 3
5 8 3 7 2 9 1 6 4 3

出力例 3

14

入力例 4

20 4
3 9 1 8 2 7 4 6 5 10 1 3 8 2 7 5 9 1 6 4

出力例 4

16

入力例 5

2 1
1000000000 1000000000

出力例 5

2000000000

Score : 466 pts

Problem Statement

Takahashi is trying to cross a river. There are N stepping stones lined up in a row in the river, numbered stone 1, stone 2, \ldots, stone N in order from the left bank. Takahashi starts on stone 1 and reaches the goal when he arrives at stone N.

From his current stone i, Takahashi can jump to any one of stone i+1, stone i+2, \ldots, stone \min(i+K,\, N). In other words, the difference in stone numbers covered in a single jump is between 1 and K inclusive, and he can only move in the direction of increasing numbers. Takahashi must land exactly on stone N at the end.

Each stepping stone i (1 \leq i \leq N) has a positive integer value A_i assigned to it. When Takahashi lands on a stone, that stone's value is added to the cumulative cost. The values of stones he does not land on are not added. The value A_1 of the starting stone 1 and the value A_N of the goal stone N are also each added when he lands on them.

Among all paths Takahashi can take from stone 1 to stone N, find the one that minimizes the cumulative cost, and output that minimum cumulative cost.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq K \leq N - 1
  • 1 \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 stepping 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 values of each stepping stone, separated by spaces.

Output

Output in one line the minimum cumulative cost when traveling from stone 1 to stone N.

Sample Input 1

5 2
1 3 2 4 1

Sample Output 1

4

Sample Input 2

6 3
10 1 1 1 1 10

Sample Output 2

21

Sample Input 3

10 3
5 8 3 7 2 9 1 6 4 3

Sample Output 3

14

Sample Input 4

20 4
3 9 1 8 2 7 4 6 5 10 1 3 8 2 7 5 9 1 6 4

Sample Output 4

16

Sample Input 5

2 1
1000000000 1000000000

Sample Output 5

2000000000