Overview

Each flower can only be made shorter.
The goal is to keep each flower as tall as possible while satisfying the constraint that “the height difference between nearby flowers is at most \(D\).”

Analysis

First, the condition that the difference between the maximum and minimum values among any \(K\) consecutive flowers is at most \(D\) is equivalent to the following:

• For any two flowers whose index difference is at most \(K-1\), their height difference is at most \(D\).

From here on, let \(L = K-1\).

In other words, if the final height of flower \(i\) is \(X_i\), then for any \(|i-j| \leq L\), we must have:

\[ |X_i-X_j|\leq D \]

Here, let’s focus on the original height of some flower \(j\), which is \(H_j\).
Since \(X_j \leq H_j\), any flower within distance \(L\) from flower \(j\) can be at most \(H_j+D\).
Furthermore, flowers within distance \(L\) from those can be at most \(H_j+2D\), and so on. The restriction propagates in this manner.

If we can move by at most \(L\) steps at a time from flower \(j\) to flower \(i\), the required number of steps is:

\[ \left\lceil \frac{|i-j|}{L} \right\rceil \]

Therefore, any achievable final height \(X_i\) must satisfy:

\[ X_i \leq H_j + D \left\lceil \frac{|i-j|}{L} \right\rceil \]

for all \(j\).

Thus, the maximum possible height for flower \(i\) is:

\[ B_i = \min_j \left( H_j + D \left\lceil \frac{|i-j|}{L} \right\rceil \right) \]

This \(B_i\) actually satisfies the condition.
This is because if \(|i-j| \leq L\), flowers \(i\) and \(j\) are within a distance of 1 step, so:

\[ B_i \leq B_j + D \]

and

\[ B_j \leq B_i + D \]

hold, which implies:

\[ |B_i-B_j|\leq D \]

In other words, it is optimal to keep each flower at height \(B_i\).

However, checking all \(j\) for each \(i\) would take \(O(N^2)\) time, which is too slow for \(N \leq 2 \times 10^5\).
Thus, we compute the restrictions from the left and right sides efficiently.

Algorithm

When \(K=1\), each interval contains only one flower, so the height difference is always \(0\).
Therefore, the answer is simply:

\[ \sum_i H_i \]

Below, we assume \(K \geq 2\), which means \(L = K-1 \geq 1\).

Let left[i] be the restriction propagated from the left side:

\[ left_i = \min_{j\leq i} \left( H_j + D \left\lceil \frac{i-j}{L} \right\rceil \right) \]

This can be computed using DP as follows:

\[ left_i = \min \left( H_i,\ \min_{i-L\leq p<i} (left_p + D) \right) \]

The meaning of this is as follows:

• The restriction from the original height of flower \(i\) itself is \(H_i\).
• The restriction propagates from some flower \(p\) within the previous \(L\) positions, increasing by \(D\).

Similarly, let right[i] be the restriction propagated from the right side:

\[ right_i = \min_{j\geq i} \left( H_j + D \left\lceil \frac{j-i}{L} \right\rceil \right) \]

This can be computed by iterating from right to left:

\[ right_i = \min \left( H_i,\ \min_{i<p\leq i+L} (right_p + D) \right) \]

Finally, since the restrictions from both sides must be satisfied simultaneously, the optimal height for flower \(i\) is:

\[ \min(left_i, right_i) \]

The answer is:

\[ \sum_i \min(left_i, right_i) \]

For example, if \(K=3, D=2, H=[10,1,10]\), then \(L=2\).
Since the height of the middle flower is at most \(1\), and the left and right flowers are within distance \(2\) from the middle, they can be at most \(1+2=3\).
Therefore, the optimal heights are \([3,1,3]\).

In each DP, we need to find the “minimum value of the previous or next \(L\) elements.”
This can be computed in \(O(N)\) overall time using a monotonic queue (sliding window minimum).

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Implementation Details

We store the candidate indices in the monotonic queue.

When computing from the left, for each \(i\):

1. Remove indices that are out of range (i.e., less than \(i-L\)) from the front of the queue.
2. The front of the queue will represent the minimum value of left within the current window.
3. Compute left[i].
4. Remove indices with values larger than left[i] from the back of the queue, then insert \(i\).

When computing from the right, perform the same process in the reverse direction.

Also, when \(K=1\), we have \(L=0\), so the DP transition cannot be applied directly. We handle this as a special case at the beginning.

Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K, D = map(int, input().split())
    H = list(map(int, input().split()))

    if K == 1:
        print(sum(H))
        return

    L = K - 1

    left = [0] * N
    dq = deque()
    for i in range(N):
        while dq and dq[0] < i - L:
            dq.popleft()

        v = H[i]
        if dq:
            t = left[dq[0]] + D
            if t < v:
                v = t
        left[i] = v

        while dq and left[dq[-1]] >= v:
            dq.pop()
        dq.append(i)

    right = [0] * N
    dq.clear()
    for i in range(N - 1, -1, -1):
        while dq and dq[0] > i + L:
            dq.popleft()

        v = H[i]
        if dq:
            t = right[dq[0]] + D
            if t < v:
                v = t
        right[i] = v

        while dq and right[dq[-1]] >= v:
            dq.pop()
        dq.append(i)

    ans = 0
    for a, b in zip(left, right):
        ans += a if a < b else b

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.