E - 花壇の手入れ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は庭師で、横一列に並んだ N 本の花の手入れを任されています。i 番目の花の現在の高さは H_i です。

依頼主の要望は「どの連続する K 本の花を見ても、その中で最も高い花と最も低い花の高さの差が D 以下になるようにしたい」というものです。

高橋君は花の茎を 切る ことしかできません（伸ばすことはできません）。各花は好きな非負整数の高さに切ることができますが、元の高さより高くすることはできません。つまり、i 番目の花の最終的な高さ H'_i は 0 \leq H'_i \leq H_i を満たす整数でなければなりません。

高橋君はできるだけ花を高く残したいので、全ての花の最終的な高さの合計 H'_1 + H'_2 + \cdots + H'_N を最大化したいと考えています。

条件を満たすように各花を切った（あるいはそのまま残した）とき、最終的な花の高さの合計の最大値を求めてください。

形式的には、以下の条件をすべて満たす整数列 H'_1, H'_2, \ldots, H'_N のうち、 \sum_{i=1}^{N} H'_i の最大値を求めてください。

  • すべての i (1 \leq i \leq N) について 0 \leq H'_i \leq H_i
  • すべての j (1 \leq j \leq N - K + 1) について \max(H'_j, H'_{j+1}, \ldots, H'_{j+K-1}) - \min(H'_j, H'_{j+1}, \ldots, H'_{j+K-1}) \leq D

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 0 \leq D \leq 10^9
  • 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N K D
H_1 H_2 \ldots H_N
  • 1 行目には、花の本数を表す N 、連続する花の本数を表す K 、許容される高さの差を表す D が、スペース区切りで与えられる。
  • 2 行目には、各花の現在の高さを表す H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。

出力

条件を満たすように花を切ったとき、最終的な花の高さの合計の最大値を 1 行で出力せよ。

入力例 1

5 3 2
3 1 4 1 5

出力例 1

11

入力例 2

6 2 0
2 2 5 5 1 1

出力例 2

6

入力例 3

12 4 5
10 3 8 15 6 7 20 12 11 4 9 14

出力例 3

89

入力例 4

30 7 10
25 40 18 33 47 12 29 55 21 36 44 9 31 50 27 16 38 60 22 35 48 14 30 53 26 41 19 37 45 11

出力例 4

576

入力例 5

1 1 0
1000000000

出力例 5

1000000000

Score : 466 pts

Problem Statement

Takahashi is a gardener in charge of caring for N flowers lined up in a row. The current height of the i-th flower is H_i.

The client's request is: "For any contiguous K flowers, the difference between the maximum height and the minimum height among them should be at most D."

Takahashi can only cut the stems of the flowers (he cannot make them grow). Each flower can be cut to any non-negative integer height, but it cannot be made taller than its original height. That is, the final height H'_i of the i-th flower must be an integer satisfying 0 \leq H'_i \leq H_i.

Since Takahashi wants to keep the flowers as tall as possible, he wants to maximize the sum of the final heights of all flowers, H'_1 + H'_2 + \cdots + H'_N.

Find the maximum possible sum of the final heights of the flowers when they are cut (or left as they are) to satisfy the conditions.

Formally, find the maximum value of \sum_{i=1}^{N} H'_i among all integer sequences H'_1, H'_2, \ldots, H'_N that satisfy the following conditions:

  • 0 \leq H'_i \leq H_i for all i (1 \leq i \leq N)
  • \max(H'_j, H'_{j+1}, \ldots, H'_{j+K-1}) - \min(H'_j, H'_{j+1}, \ldots, H'_{j+K-1}) \leq D for all j (1 \leq j \leq N - K + 1)

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 0 \leq D \leq 10^9
  • 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N K D
H_1 H_2 \ldots H_N
  • The first line contains the number of flowers N, the number of contiguous flowers K, and the allowed height difference D, separated by spaces.
  • The second line contains the current heights of the flowers H_1, H_2, \ldots, H_N, separated by spaces.

Output

Print the maximum possible sum of the final heights of the flowers when they are cut to satisfy the conditions in a single line.

Sample Input 1

5 3 2
3 1 4 1 5

Sample Output 1

11

Sample Input 2

6 2 0
2 2 5 5 1 1

Sample Output 2

6

Sample Input 3

12 4 5
10 3 8 15 6 7 20 12 11 4 9 14

Sample Output 3

89

Sample Input 4

30 7 10
25 40 18 33 47 12 29 55 21 36 44 9 31 50 27 16 38 60 22 35 48 14 30 53 26 41 19 37 45 11

Sample Output 4

576

Sample Input 5

1 1 0
1000000000

Sample Output 5

1000000000