Overview

This problem asks us to maximize the sum of heights of \(N\) flowers lined up in a row, while ensuring that for any contiguous range of \(K\) flowers, the difference between the tallest and shortest flower is at most \(D\).

By reformulating the condition into a form similar to the shortest path problem on a graph (Dijkstra’s algorithm), we can solve it efficiently with a time complexity of \(O(N \log N)\).

---

Analysis

1. Reformulating the Condition

The condition “the difference between the maximum and minimum heights among any \(K\) consecutive flowers is at most \(D\)” can be reformulated as follows:

“For any two flowers \(i, j\) with a distance of at most \(K-1\), the difference in their heights is at most \(D\) (i.e., \(|H'_i - H'_j| \le D\)).”

This is because any two flowers at a distance of at most \(K-1\) are always contained together in some “consecutive range of \(K\) flowers”, so their difference must be at most \(D\). Conversely, if the difference between every pair at a distance of at most \(K-1\) is at most \(D\), then the difference between the maximum and minimum in any interval of length \(K\) will also be at most \(D\).

Therefore, the final height \(H'_i\) of each flower \(i\) must be at most its original height \(H_i\), and additionally, at most the height of any other flower \(j\) within distance \(K-1\) plus \(D\).

Expressed mathematically, this is: $\(H'_i = \min \left( H_i, \min_{|i-j| \le K-1} (H'_j + D) \right)\)$

2. Why Can It Be Solved Like Dijkstra’s Algorithm?

The formula above is very similar to the “shortest distance update formula for vertices” in the shortest path problem on graphs (specifically, Dijkstra’s algorithm).

A flower with a lower height imposes a stricter upper bound on the heights of surrounding flowers, limiting them to “its own height \(+ D\)”. Therefore, an effective approach is to propagate the “height constraints” to surrounding flowers (within distance \(K-1\)) in ascending order of their final heights.

Specifically, we pop the flower \(u\) with the lowest temporary height and finalize its height. Then, for any unfinalized flower \(v\) within distance \(K-1\) from \(u\), we update its height to \(\min(H_v, H'_u + D)\).

3. Optimization Techniques (Using std::set)

A naive search and update of all flowers within distance \(K-1\) would take \(O(N \cdot K)\) time, which will result in a Time Limit Exceeded (TLE) when \(K\) is large.

However, once a flower \(v\) has its height updated (i.e., finalized) due to a constraint from another flower, it will never receive a tighter (lower) constraint from any other flower later. Therefore, if we can efficiently find only the indices of flowers whose heights have not yet been finalized (updated), we can avoid redundant searches.

This can be resolved by managing the unfinalized indices using std::set, which is a binary search tree. When searching for unfinalized flowers within distance \(K-1\) from a finalized flower \(u\), we can use lower_bound on the set to quickly find and iterate through the unfinalized flowers in the range \([u - (K-1), u + (K-1)]\), updating them and removing them from the set at the same time.

---

Algorithm

1. Handling Corner Cases When \(K=1\), there are no constraints between different flowers. Thus, we do not need to cut any flowers, and the sum of the initial heights \(\sum H_i\) is the answer.

2. Initialization

   • Let \(L = K - 1\).
   • Prepare an array \(F\) to store the final height of each flower, and copy \(H\) to it as initial values.
   • Add all indices \(0, 1, \ldots, N-1\) to active_indices (a std::set), which manages the indices that are not yet finalized.
   • Add (initial height, index) for all flowers to a priority queue pq.

3. Dijkstra-like Propagation Process Repeat the following until pq is empty:

   • Pop the element (d, u) with the lowest height from pq.
   • If u is already finalized (visited), skip it.
   • Mark u as visited and remove it from active_indices.
   • Search for indices \(v\) within the range \([u - L, u + L]\) in active_indices using lower_bound.
   • For each such \(v\) that satisfies the condition:
     • Update \(F_v\) to \(\min(H_v, d + D)\).
     • Push the updated (F[v], v) into pq.
     • Consider \(v\) finalized and remove it from active_indices.

4. Outputting the Answer Calculate and output the sum of the elements in the final array \(F\).

---

Complexity

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

  • Each element is added to active_indices (std::set) at most once and removed at most once.
  • The search and deletion operations using lower_bound are performed at most \(N\) times in total (amortized analysis).
  • The push and pop operations on the priority queue are also performed at most a few times per element (during initialization and updates), resulting in an overall time complexity of \(O(N \log N)\), which is fast enough.

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

  • The sizes of the arrays \(H, F\), the visited flags, the std::set, and the priority queue are all proportional to at most \(N\), which easily fits within the memory limit.

---

Implementation Points

• Efficient Deletion from std::set In C++, when deleting elements within a range from a std::set while advancing the iterator in a loop, writing it = active_indices.erase(it) allows you to delete the element and obtain a valid iterator pointing to the next element in \(O(1)\) amortized time.

• Preventing Overflow Since the heights of the flowers, their sum, and the tolerance \(D\) can be very large values (up to \(10^9\) or \(N \times 10^9\)), it is necessary to use 64-bit integer types like long long in C++.

  Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    long long D;
    if (!(cin >> N >> K >> D)) return 0;

    vector<long long> H(N);
    long long sum_H = 0;
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
        sum_H += H[i];
    }

    // Corner case: if K = 1, there are no constraints between different flowers.
    if (K == 1) {
        cout << sum_H << "\n";
        return 0;
    }

    long long L = K - 1;

    vector<long long> F(N);
    vector<bool> visited(N, false);
    set<int> active_indices;
    using P = pair<long long, int>;
    priority_queue<P, vector<P>, greater<P>> pq;

    for (int i = 0; i < N; ++i) {
        active_indices.insert(i);
        pq.push({H[i], i});
        F[i] = H[i];
    }

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        if (active_indices.count(u)) {
            active_indices.erase(u);
        }

        long long l = max(0LL, u - L);
        long long r = min((long long)N - 1, u + L);

        // Find all active indices in the range [u - L, u + L]
        auto it = active_indices.lower_bound(l);
        while (it != active_indices.end() && *it <= r) {
            int v = *it;
            if (H[v] > d + D) {
                F[v] = d + D;
                pq.push({F[v], v});
            } else {
                F[v] = H[v];
                pq.push({F[v], v});
            }
            // Erase from set and get the next iterator in O(1) amortized time
            it = active_indices.erase(it);
        }
    }

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += F[i];
    }

    cout << ans << "\n";

    return 0;
}

---

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