Overview

From \(M\) points arranged in a straight line, select \(N\) points such that the distance between any two adjacent selected points is at least \(K\).
If a valid selection exists, find the maximum distance between the leftmost and rightmost selected points.

Analysis

Let the coordinate of point \(1\) be \(0\), and the coordinate of point \(i\) be \(P_i\).
The total length of the flower bed is

\(P_M - P_1 = P_M\)

The distance between the leftmost and rightmost selected points obviously cannot exceed the total length of the flower bed \(P_M\).

Here is an important observation.

Suppose there exists at least one valid selection satisfying the conditions.
Let that selection, ordered from left to right, be

\(x_1, x_2, \dots, x_N\)

When \(N \geq 2\), even if we move the leftmost point \(x_1\) to point \(1\), i.e., coordinate \(0\),

\(x_2 - 0 \geq x_2 - x_1 \geq K\)

so the condition is not violated.

Similarly, even if we move the rightmost point \(x_N\) to point \(M\), i.e., coordinate \(P_M\),

\(P_M - x_{N-1} \geq x_N - x_{N-1} \geq K\)

so the condition is not violated.

Therefore, if \(N \geq 2\) and a valid selection exists, we can always select both point \(1\) and point \(M\), and the answer is the total length of the flower bed \(P_M\).

In other words, this problem can be rephrased as follows:

• If \(N = 1\), the answer is always \(0\)
• If \(N \geq 2\), and we can select \(N\) points satisfying the condition, the answer is the total length
• If we cannot, the answer is -1

All that remains is to determine “what is the maximum number of points we can select such that the distance between consecutive selections is at least \(K\)?”

Naively trying all combinations results in an enormous number of possibilities, which is far too slow.
Also, using DP to consider “where to place the \(i\)-th point” would be \(O(NM)\), and since the maximum is \(5 \times 10^5\), this is also too slow.

Instead, we use a greedy approach: scanning from left to right, “place a point as soon as possible.”

By placing points as far left as possible, we maximize the remaining space available afterward.
Therefore, this greedy approach maximizes the number of points we can select.

Algorithm

Set the coordinate of point \(1\) to \(0\), and compute coordinates from left to right.

1. First, select point \(1\)
   
   • cnt = 1
   • Set the last selected coordinate to last = 0
2. Compute the coordinate coord of each point from left to right
3. If coord - last >= K, select that point
   • Increment cnt by \(1\)
   • Set last = coord
4. After processing all points, let total be the total length of the flower bed
5. Determine the answer
   • If \(N = 1\), output 0
   • If cnt >= N, output total
   • Otherwise, output -1

For example, consider coordinates

\(0, 4, 10, 13, 21\)

with \(K = 7\).

Greedily selecting from left:

• First, select \(0\)
• \(4\) has distance \(4\), so it cannot be selected
• \(10\) has distance \(10\), so select it
• \(13\) has distance \(3\) from the previous \(10\), so it cannot be selected
• \(21\) has distance \(11\) from the previous \(10\), so select it

Thus, we can select \(3\) points.
If \(N = 3\), a valid selection exists, so the answer is the total length \(21\).

Complexity

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

Implementation Notes

Since the sum of distances can be large, coordinates and distances should be handled with long long.

Also, there is no need to store each \(D_i\) in an array.
It is sufficient to update the current coordinate while reading input and greedily determine on the spot whether to select the point.

When \(N = 1\), the leftmost and rightmost selected points are the same point, so the answer is always \(0\).

Source Code

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

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

    int N, M;
    long long K;
    cin >> N >> M >> K;

    long long coord = 0;
    long long total = 0;

    int cnt = 1;
    long long last = 0;

    for (int i = 1; i <= M - 1; i++) {
        long long d;
        cin >> d;
        coord += d;
        if (coord - last >= K) {
            cnt++;
            last = coord;
        }
    }
    total = coord;

    if (N == 1) {
        cout << 0 << '\n';
    } else if (cnt >= N) {
        cout << total << '\n';
    } else {
        cout << -1 << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-high.