Overview

We want to adjust the heights of \(N\) flowers lined up in a row so that for any contiguous \(K\) flowers, the condition “maximum height \(-\) minimum height \(\leq D\)” is satisfied. Under the condition that flowers can only be cut (i.e., their heights can only be decreased), the goal is to maximize the sum of the final heights of the flowers.

Discussion

To satisfy the condition “the difference between the maximum and minimum heights of any contiguous \(K\) flowers is at most \(D\)”, a flower \(i\) must not be too tall compared to other flowers in any contiguous window of size \(K\) that contains \(i\).

Specifically, the height of flower \(i\) must be at most the minimum height among the \(K-1\) flowers to its left plus \(D\). At the same time, it must be at most the minimum height among the \(K-1\) flowers to its right plus \(D\).

A naive approach of checking all intervals would take \(O(NK)\) time, which will exceed the time limit. Therefore, we can approach the problem as follows: 1. Constraint from the left (array \(L\)): Processing the flowers from left to right, let \(m\) be the minimum value of \(L\) among the previous \(K-1\) flowers for flower \(i\). The height of flower \(i\) is constrained to \(\min(H_i, m + D)\). 2. Constraint from the right (array \(R\)): Processing the flowers from right to left, let \(m'\) be the minimum value of \(R\) among the next \(K-1\) flowers for flower \(i\). The height of flower \(i\) is constrained to \(\min(H_i, m' + D)\).

The optimal final height of flower \(i\) must satisfy both the left and right constraints, so it will be \(H'_i = \min(L_i, R_i)\). Since we only need to find the “sliding window minimum of width \(K-1\)” for each direction, this can be computed in \(O(N)\) using a sliding window minimum (Monotone Queue) algorithm.

Algorithm

1. When \(K = 1\), there are no constraints to satisfy, so we can directly output the sum of the initial heights \(\sum H_i\).
2. When \(K \geq 2\), we use a deque (double-ended queue) to compute the sliding window minimum of width \(c = K-1\).
3. Propagation from the left:
   • Loop \(i\) from \(0\) to \(N-1\).
   • Remove elements from the front of the queue if they fall outside the range \([i - c, i - 1]\).
   • If the queue is not empty, retrieve the minimum value \(m\) and set \(L_i = \min(H_i, m + D)\). If the queue is empty, set \(L_i = H_i\).
   • Add \(L_i\) to the queue. Before adding, remove all values greater than or equal to \(L_i\) from the back of the queue to maintain the monotonic increasing order.
4. Propagation from the right:
   • Loop \(i\) backwards from \(N-1\) to \(0\) and compute \(R_i\) in the same manner.
5. For each \(i\), calculate \(\min(L_i, R_i)\) and output their sum.

Complexity

• Time Complexity: \(O(N)\). This is because each element is added to and removed from the deque at most once.
• Space Complexity: \(O(N)\). The sizes of the arrays \(H, L, R\) and the deque are proportional to \(N\).

Key Implementation Points

• In Python, while the standard collections.deque can be used, simulating a deque using an array with head and tail pointers can improve the constant factor speed.

• Storing “indices” instead of “actual values” in the sliding minimum queue makes it easier to check for out-of-bounds elements.

• When removing elements from the back of the queue, compare using >= to maintain monotonicity.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    H = list(map(int, input_data[3:3+N]))
    
    if K == 1:
        print(sum(H))
        return
        
    c = K - 1
    
    L = [0] * N
    dq = [0] * N
    head = 0
    tail = 0
    
    for i in range(N):
        while head < tail and dq[head] < i - c:
            head += 1
        
        if head < tail:
            min_val = L[dq[head]]
            val = min_val + D
            L[i] = H[i] if H[i] < val else val
        else:
            L[i] = H[i]
            
        while head < tail and L[dq[tail - 1]] >= L[i]:
            tail -= 1
        dq[tail] = i
        tail += 1
        
    R = [0] * N
    head = 0
    tail = 0
    
    for i in range(N - 1, -1, -1):
        while head < tail and dq[head] > i + c:
            head += 1
            
        if head < tail:
            min_val = R[dq[head]]
            val = min_val + D
            R[i] = H[i] if H[i] < val else val
        else:
            R[i] = H[i]
            
        while head < tail and R[dq[tail - 1]] >= R[i]:
            tail -= 1
        dq[tail] = i
        tail += 1
        
    ans = 0
    for i in range(N):
        l_val = L[i]
        r_val = R[i]
        ans += l_val if l_val < r_val else r_val
        
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.