Overview

In this problem, given a sequence \(H\) of length \(N\), we want to maximize the sum of a sequence \(H'\) obtained by decreasing each element of \(H\) to a value less than or equal to its original value, subject to the condition: “for any contiguous interval of length \(K\), the difference between the maximum and minimum values is at most \(D\).”

Analysis

1. Reformulating the Condition

Consider the condition: “for any interval of length \(K\), the difference between the maximum and minimum values is at most \(D\).” If we let \(i, j\) be the indices of any two elements within the interval, the distance between them is at most \(K-1\). Therefore, this condition can be rephrased as follows: * Letting \(L = K - 1\), for any \(i, j\), \(|i - j| \leq L \implies |H'_i - H'_j| \leq D\).

Furthermore, this is equivalent to: “for all \(i, j\), \(|i - j| \leq L \implies H'_i \leq H'_j + D\).”

2. Formulating the Maximum Value of Each Element

We want to make each \(H'_i\) as large as possible while satisfying both the original height constraint \(H'_i \leq H_i\) and the above difference constraints. If the height of some element \(j\) is \(H_j\), the allowed height increases by \(D\) for every distance \(L\) away from \(j\). Therefore, considering the constraints from all \(j\), the final height \(H'_i\) is determined as follows:

\[H'_i = \min_{1 \leq j \leq N} \left( H_j + \lceil \frac{|i - j|}{L} \rceil D \right)\]

(Note that when \(i = j\), this is \(H_i\))

Naively calculating this formula for all \(i\) would take \(O(N^2)\) time, which will result in a Time Limit Exceeded (TLE) under the constraint \(N \leq 2 \times 10^5\).

3. Decomposition into Left/Right Contributions and Optimization

To speed up the computation, we decompose the constraints into \(f[i]\), the constraint from the elements to the left (\(j < i\)), and \(g[i]\), the constraint from the elements to the right (\(j > i\)).

\[H'_i = \min(H_i, f[i], g[i])\]

Here, the constraint from the left side, \(f[i]\), is defined as follows: $\(f[i] = \min_{j < i} \left( H_j + \lceil \frac{i - j}{L} \rceil D \right)\)$

Let us split this expression into the nearest \(L\) elements (the range where \(\lceil \frac{i-j}{L} \rceil = 1\)) and the elements further to the left. $\(f[i] = \min \left( \min_{i-L \leq j < i} (H_j + D), \min_{j < i-L} (H_j + \lceil \frac{i - j}{L} \rceil D) \right)\)$

Here, since \(\lceil \frac{i-j}{L} \rceil = \lceil \frac{i-L-j}{L} \rceil + 1\) holds when \(j < i-L\), we can rearrange it as follows: $\(f[i] = \min \left( \min_{i-L \leq j < i} H_j, \min_{j < i-L} (H_j + \lceil \frac{i-L-j}{L} \rceil D) \right) + D\)$

The term on the right is exactly \(f[i-L]\) itself. Thus, we obtain the following simple recurrence relation: $\(f[i] = \min \left( \min_{i-L \leq j < i} H_j, f[i-L] \right) + D\)$

If we let \(M[i] = \min_{i-L \leq j < i} H_j\), we can express it as: $\(f[i] = \min(M[i], f[i-L]) + D\)$

\(M[i]\) can be computed in overall \(O(N)\) time using the sliding window minimum algorithm. Using this, we can find \(f[i]\) for all \(i\) in \(O(N)\) time.

The constraint from the right side, \(g[i]\), can also be found in \(O(N)\) time in a similar manner by reversing the array \(H\) and applying the same process.

Algorithm

1. Handling Corner Cases: When \(K = 1\), there is practically no constraint on the height difference, so we output the sum of the original heights, \(\sum H_i\), as is.
2. Computing Sliding Window Minimums: Using a double-ended queue (deque), compute the minimum value \(M[i]\) of the nearest \(L = K - 1\) elements for each \(i\).
3. Computing the Left Constraint \(f\): Determine \(f[i]\) from left to right using the recurrence relation \(f[i] = \min(M[i], f[i-L]) + D\).
4. Computing the Right Constraint \(g\): Perform the same process on the reversed array \(H\), and reverse the resulting array again to obtain \(g[i]\).
5. Calculating the Answer: For each \(i\), compute \(\min(H_i, f[i], g[i])\) and output their sum.

Complexity

• Time Complexity: \(O(N)\) In the sliding window minimum computation, each element is added to the deque at most once and removed at most once, which runs in \(O(N)\) time overall. Since the recurrence computation and the array reversal can also be done in \(O(N)\) time, the overall time complexity is \(O(N)\), which is well within the time limit.
• Space Complexity: \(O(N)\) In addition to the original array \(H\), we use \(O(N)\) memory to store the constraint arrays \(f, g\) and the deque.

Implementation Details

• Code Reuse via Array Reversal: When finding the right-side constraint \(g\), instead of writing a new process, we reverse the input array (H[::-1]), pass it to the same function get_f, and then reverse the result back (g_rev[::-1]). This keeps the implementation simple and prevents bugs.

• Boundary Conditions for Indices: If \(i - L < 0\), the previous step (\(f[i-L]\)) does not exist, so we handle it as INF (a sufficiently large value).

  Source Code

import sys
from collections import deque

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    D = int(data[2])
    H = [int(x) for x in data[3:]]
    
    if K == 1:
        print(sum(H))
        return
        
    L = K - 1
    INF = 10**18
    
    def get_f(A):
        M = [INF] * N
        q = deque()
        for i in range(N):
            if i > 0:
                val = A[i-1]
                while q and A[q[-1]] >= val:
                    q.pop()
                q.append(i-1)
            if q and q[0] < i - L:
                q.popleft()
            if q:
                M[i] = A[q[0]]
        
        f = [INF] * N
        for i in range(1, N):
            prev_val = f[i-L] if i-L >= 0 else INF
            cand = M[i] if M[i] < prev_val else prev_val
            f[i] = cand + D
        return f

    f = get_f(H)
    H_rev = H[::-1]
    g_rev = get_f(H_rev)
    g = g_rev[::-1]
    
    ans = 0
    for i in range(N):
        val = H[i]
        if f[i] < val:
            val = f[i]
        if g[i] < val:
            val = g[i]
        ans += val
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.