Overview

In a situation where we can only decrease the height of each flower, we want to maximize the sum of the final heights such that the difference between the maximum and minimum heights in any contiguous \(K\) flowers is at most \(D\).

The key is to rephrase the condition on intervals of length \(K\) into the condition: “the difference in height between any two flowers with a distance of at most \(K-1\) is at most \(D\).”

Observation

Let \(L = K - 1\).

The distance between any two flowers within any contiguous \(K\) flowers is at most \(K-1 = L\).
Conversely, any two flowers with a distance of at most \(L\) are always contained together in some interval of length \(K\).

Therefore, the condition can be rephrased as follows:

• For all \(|i-j| \leq L\), \(|H'_i - H'_j| \leq D\)

In other words, flowers within a distance of \(L\) must have a height difference of at most \(D\).

---

The height of flower \(j\) is at most \(H_j\).
If \(|i-j| \leq L\), the height of flower \(i\) cannot be more than \(D\) higher than flower \(j\), so:

\(H'_i \leq H_j + D\)

Furthermore, even if they are not directly within distance \(L\), the constraints propagate.

For example, if \(K=3\), then \(L=2\), so the difference is directly at most \(D\) up to 2 steps away.
If we move from position \(j\) to position \(i\) in steps of at most \(L\), the upper bound on the height increases by \(D\) for each step.

That is, if we let \(\mathrm{dist}(j,i)\) be the minimum number of steps from flower \(j\) to flower \(i\), then:

\(H'_i \leq H_j + D \times \mathrm{dist}(j,i)\)

holds.

Therefore, the minimum of the upper bounds coming from all \(j\):

\(F_i = \min_j \left( H_j + D \times \mathrm{dist}(j,i) \right)\)

will be the maximum possible height for flower \(i\).

If we find this \(F_i\) for all \(i\), the answer is:

\(\sum_i F_i\)

---

However, checking all pairs of \(i, j\) would take \(O(N^2)\) time, which is too slow for \(N \leq 2 \times 10^5\).

Thus, we calculate the constraints coming from the left and those coming from the right separately.

Algorithm

Let’s consider only the constraints received from the flowers on the left.

Let \(dp_i\) be the maximum possible height of the flower at position \(i\) considering only the constraints from the flowers at or before position \(i\).

Since there is a restriction from the original height of flower \(i\) itself, we first have:

\(dp_i \leq H_i\)

Also, the flower that transmits the constraint directly to position \(i\) is located somewhere between position \(i-L\) and \(i-1\).
The constraint from the flower with the smallest \(dp\) in this range is the strictest, so:

\(dp_i = \min \left( H_i,\ \min_{i-L \leq p < i} dp_p + D \right)\)

holds.

Calculating this formula directly takes \(O(NK)\) because we look at up to \(L\) elements for each \(i\).

To avoid this, we can find the minimum value of \(dp\) in the interval

\([i-L, i-1]\)

efficiently using a monotonic queue (or sliding window minimum).

We store candidate indices in the monotonic queue and maintain them in ascending order of their \(dp\) values.
This allows us to find the minimum value in the interval simply by looking at the front of the queue.

---

We want to perform the same process for constraints from the right. In the code, we reverse the array and reuse the same calc_left function.

The procedure is as follows:

1. Let \(L = K - 1\).
2. Run calc_left on the original array to find the constraints from the left, left.
3. Reverse the array.
4. Run calc_left on the reversed array to find the constraints from the right.
5. The constraint from the right corresponding to the original position \(i\) is rleft[N-1-i].
6. The final height is:

\(\min(\mathrm{left}_i,\ \mathrm{right}_i)\)

1. Sum these values up.

In calc_left, each index is pushed into and popped from the queue at most once, so the overall time complexity is \(O(N)\).

Complexity

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

Implementation Details

• The answer can be up to around \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), so we use long long.

• When \(K=1\), \(L=0\). Since each interval contains only one flower, there are no constraints. In this case, the code naturally yields dp[i] = H[i].

• In the monotonic queue, we remove indices that have fallen out of range from the front.

  • In 0-indexed notation, if the current position is i, the valid range is [i-L, i-1].
  • Therefore, we remove the element if dq.front() < i - L.

• To keep the dp values in the queue monotonically increasing, we pop elements from the back if their dp value is greater than or equal to the current dp[i] before pushing i.

  Source Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<ll> calc_left(const vector<ll>& H, int L, ll D) {
    int N = (int)H.size();
    vector<ll> dp(N);
    deque<int> dq;

    for (int i = 0; i < N; i++) {
        while (!dq.empty() && dq.front() < i - L) dq.pop_front();

        ll v = H[i];
        if (!dq.empty()) v = min(v, dp[dq.front()] + D);
        dp[i] = v;

        while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
        dq.push_back(i);
    }

    return dp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    ll D;
    cin >> N >> K >> D;

    vector<ll> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    int L = K - 1;

    vector<ll> left = calc_left(H, L, D);

    vector<ll> RH = H;
    reverse(RH.begin(), RH.end());
    vector<ll> rleft = calc_left(RH, L, D);

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += min(left[i], rleft[N - 1 - i]);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.