Overview

Given \(M\) points arranged on a line, select \(N\) points such that the distance between any two adjacent selected points is at least \(K\), while maximizing the distance between the “leftmost” and “rightmost” selected points.

Analysis

1. What is the maximum value?

Let \(L\) be the leftmost selected point and \(R\) be the rightmost selected point. The desired distance is \(X_R - X_L\) (where \(X_i\) is the coordinate of point \(i\)).

Since we want to maximize this distance, ideally we would like to choose point \(1\) (coordinate \(X_0\)) as the leftmost point and point \(M\) (coordinate \(X_{M-1}\)) as the rightmost point. If this is possible, the maximum value is the distance from one end to the other, namely \(X_{M-1} - X_0\).

In fact, if a valid selection satisfying the conditions exists, the maximum value is always \(X_{M-1} - X_0\).

2. Why is the total length always the maximum value?

Consider a simulation where we “fix the left end at point \(1\) and greedily place \(N\) flowers moving to the right, keeping gaps of at least \(K\) (placing as far left as possible).”

Suppose in this simulation, the last (\(N\)-th) flower is placed at point \(P\). - When \(P \leq M\) (placement succeeds): Even if we move the last (\(N\)-th) flower from point \(P\) further to the right to point \(M\), the distance to the adjacent flower only increases, so the constraint (distance \(\geq K\)) remains satisfied. Therefore, a valid arrangement with left end at \(1\) and right end at \(M\) always exists. The distance in this case is \(X_{M-1} - X_0\). - When placement becomes impossible midway: If we cannot place \(N\) flowers even when packing them as tightly as possible from the left end, then no valid arrangement satisfying the conditions exists regardless of how we choose. Therefore, the answer is -1.

From this analysis, the problem reduces to the decision problem: “Can we greedily place \(N\) flowers starting from the left end?”

3. Optimization Techniques

The coordinate \(X\) of each point can be precomputed by taking the cumulative sum of adjacent distances \(D_i\). When searching for the next placement point from left to right, naively checking one by one takes \(O(NM)\) time in the worst case, which will not fit within the time limit.

Since the coordinate array \(X\) is sorted in ascending order, we can use binary search (std::lower_bound) to efficiently find the next point that is at least distance \(K\) away from the current position in \(O(\log M)\).

---

Algorithm

1. Prepare coordinates: Compute the coordinate of each point using cumulative sums and store them in array \(X\). Set \(X_0 = 0\), and \(X_{i+1} = X_i + D_i\).

2. Handle corner cases: If \(N = 1\), the leftmost and rightmost points are the same, so the distance is always 0.

3. Greedy simulation:

   • Place the \(1\)st flower at \(X_0\) (point \(1\)).
   • If the \(i\)-th flower is placed at coordinate curr, then place the \((i+1)\)-th flower at the leftmost point with coordinate at least curr + K. Use binary search (lower_bound) for this search.
   • Repeat until \(N\) flowers are placed. If placement becomes impossible midway, no valid arrangement satisfying the conditions exists, so output -1.

4. Output the answer: If all \(N\) flowers can be placed, output the maximum distance \(X_{M-1} - X_0\).

---

Complexity

• Time complexity: \(O(M + N \log M)\)

  • Computing coordinates via cumulative sums takes \(O(M)\).
  • In the greedy simulation, binary search is performed \(N-1\) times, so this part is \(O(N \log M)\).
  • Overall, this comfortably fits within the time limit.

• Space complexity: \(O(M)\)

  • \(O(M)\) memory is used for the array \(X\) that stores the coordinates of each point.

---

Implementation Notes

• Attention to types: The total sum of distances and \(K\) can become very large values (up to approximately \(5 \times 10^{14}\)), so in C++ you need to use long long type to prevent overflow.

• Using binary search: By using std::lower_bound, you can obtain the minimum index satisfying the condition in \(O(\log M)\). Be careful about boundary condition handling when the element is not found (it == X.end()).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<long long> D(M - 1);
    for (int i = 0; i < M - 1; ++i) {
        cin >> D[i];
    }

    // Corner case: If only 1 flower is to be planted, the distance is always 0.
    if (N == 1) {
        cout << 0 << "\n";
        return 0;
    }

    // X[i] stores the coordinate of point i+1 (0-indexed)
    vector<long long> X(M, 0);
    for (int i = 0; i < M - 1; ++i) {
        X[i + 1] = X[i] + D[i];
    }

    // Greedy simulation to check if it's possible to place N flowers
    int curr = 0;
    bool possible = true;
    for (int step = 1; step < N; ++step) {
        long long target = X[curr] + K;
        auto it = lower_bound(X.begin(), X.end(), target);
        if (it == X.end()) {
            possible = false;
            break;
        }
        curr = distance(X.begin(), it);
    }

    // If a valid configuration exists, the maximum distance is always the total length X[M-1] - X[0].
    if (possible) {
        cout << X[M - 1] << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

---

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