Overview

Select \(N\) points from \(M\) points such that the distance between any two adjacent selected points is at least \(K\).
If the condition can be satisfied, find the maximum distance between the leftmost and rightmost selected points.

Analysis

Consider the coordinates of each point, with point \(1\) at the left end as \(0\).

For example, if the distances are

\(D = [2, 3, 4, 2]\)

then the coordinates of each point are

\(0, 2, 5, 9, 11\)

---

The key insight is as follows.

If a valid selection exists, we can always include both endpoints

Let the \(N\) selected points from left to right be

\(p_1, p_2, \dots, p_N\)

If this selection satisfies the condition, replacing the leftmost selected point \(p_1\) with point \(1\) will not decrease the distance to the next point.

Similarly, replacing the rightmost selected point \(p_N\) with point \(M\) will not decrease the distance from the previous point.

In other words, if a valid selection exists, then a valid selection that includes both point \(1\) and point \(M\) also exists.

Therefore, when \(N \geq 2\), the answer is one of the following:

• If a valid selection exists, the answer is the distance from point \(1\) to point \(M\)
• If none exists, the answer is \(-1\)

The distance from point \(1\) to point \(M\) is the sum of all \(D_i\).

---

All that remains is to determine “whether we can select \(N\) points satisfying the condition”

Whether the condition can be satisfied can be determined using a greedy approach.

We scan from left to right, and whenever the distance from the last selected point is at least \(K\), we select that point.

This is the “pack as far left as possible” method.

By selecting the next point as early as possible, we maximize the remaining room for future selections.
Therefore, if this greedy method cannot select \(N\) points, no selection method can select \(N\) points.

---

Why a naive approach is difficult

Exhaustive search of selecting \(N\) points from \(M\) results in an extremely large number of combinations.

Also, if we use dynamic programming to track “how many points have been selected” and “where was the last selected point,” it becomes \(O(NM)\) in the worst case, which is too slow for the constraint \(M \leq 5 \times 10^5\).

In this problem, by leveraging the fact that the answer is either “the total length” or “\(-1\)”, we can solve it in linear time.

Algorithm

If \(N = 1\), only one point is selected, so the leftmost and rightmost are the same point.
Therefore the answer is always \(0\).

If \(N \geq 2\), do the following:

1. Start with point \(1\) selected
2. Scan the points from left to right
3. If the distance from the last selected point is at least \(K\), select that point
4. If \(N\) points can be selected, the condition is satisfiable
5. Finally,
   • If \(N\) or more points can be selected, the answer is the total distance
   • Otherwise, the answer is \(-1\)

In the code, the following variables are used:

• total: The total distance from point \(1\) to the current point; ultimately the total distance
• cur: The coordinate of the current point being examined
• last: The coordinate of the last selected point
• cnt: The number of points currently selected

For example, consider the coordinates

\(0, 2, 5, 9, 11\)

with \(K = 4\), \(N = 3\).

• First, select coordinate \(0\)
• Coordinate \(2\) has distance \(2\), so it cannot be selected
• Coordinate \(5\) has distance \(5\), so select it
• Coordinate \(9\) has distance \(4\), so select it

This selects \(3\) points, so the condition is satisfiable.
Therefore the answer is the total distance \(11\).

In practice, by selecting coordinates \(0, 5, 11\), we can use both endpoints and achieve a distance of \(11\).

Complexity

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

Implementation Notes

Since the sum of \(D_i\) can be large, in other languages you need to use 64-bit integer types such as long long.

In Python, there is no need to worry about integer overflow.

Also, when \(N = 1\), there are no adjacent flowers, so the constraint is always satisfied, and the answer is \(0\).

Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    K = next(it)

    if N == 1:
        print(0)
        return

    total = 0
    cur = 0
    last = 0
    cnt = 1

    for d in it:
        total += d
        cur += d
        if cnt < N and cur - last >= K:
            cnt += 1
            last = cur

    print(total if cnt >= N else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.