Overview

This problem asks you to select \(N\) points from \(M\) points arranged in a straight line such that the distance between any two adjacent selected points is at least \(K\) meters, and maximize the “distance from the leftmost to the rightmost” selected point. If no valid selection exists, output -1.

---

Analysis

1. Key Insight: The maximum distance is always “the distance from one end to the other”

The most important point of this problem is that “if a valid selection exists, the maximum distance is always achieved by selecting the leftmost point \(1\) and the rightmost point \(M\).”

Let’s consider why this holds. Assume there exists a valid selection of \(N\) points \(p_1 < p_2 < \dots < p_N\) satisfying the condition. In this case: - Change the leftmost point \(p_1\) to “point \(1\)”, which is further to the left - Change the rightmost point \(p_N\) to “point \(M\)”, which is further to the right

Even after performing these operations, the distances between adjacent points (\(p_2 - p_1\) and \(p_N - p_{N-1}\)) only increase, so the constraint that adjacent distances must be at least \(K\) is never violated.

Therefore, if at least one valid selection exists, then a valid selection that includes both the leftmost (point \(1\)) and rightmost (point \(M\)) also necessarily exists. Thus, the maximum distance is always the total length (the distance from point \(1\) to point \(M\)).

2. Determining whether a valid selection exists

So how do we determine whether a valid selection exists (i.e., whether we can place \(N\) points with adjacent distances of at least \(K\))?

This can be determined using a greedy approach of “selecting points as far left as possible.” 1. Fix the 1st point at the leftmost “point \(1\)”. 2. For the 2nd point, select “the leftmost point that is at least distance \(K\) away from the 1st point.” 3. For the 3rd point, select “the leftmost point that is at least distance \(K\) away from the 2nd point.” 4. Repeat this until \(N\) points have been selected.

If all \(N\) points can be selected using this method (i.e., the last point’s index is at most \(M\)), then a valid arrangement exists. If at any point we run out of available points, then it is impossible to place \(N\) points regardless of how we choose them, so there is no solution (-1).

---

Algorithm

1. Computing the coordinates of each point From the distances \(D_i\) between adjacent points, compute the coordinates \(X_0, X_1, \dots, X_{M-1}\) of each point using prefix sums, with point \(1\) at the origin \(0\).

   • \(X_0 = 0\)
   • \(X_i = X_{i-1} + D_{i-1} \quad (1 \leq i \leq M-1)\)

2. Greedy determination (two-pointer-like pointer traversal) Let curr_idx be the index of the currently selected point. To find the next candidate point, search for the smallest next_idx satisfying X[next_idx] >= X[curr_idx] + K. Repeat this \(N-1\) times.

   • If next_idx exceeds \(M\), it is impossible to find a valid arrangement, so output -1.
   • If all \(N\) points are successfully selected, output the total length \(X_{M-1}\).

---

Complexity

• Time complexity: \(O(M)\)
  • Building the coordinate array \(X\) takes \(O(M)\).
  • In the greedy search, the pointer next_idx only moves to the right (never backtracks), so it is incremented at most \(M\) times in total. Therefore, the determination part also runs in \(O(M)\).
• Space complexity: \(O(M)\)
  • \(O(M)\) memory is used for the array \(X\) that stores the coordinates of each point.

---

Implementation Notes

• Corner case when \(N = 1\) When \(N = 1\), the leftmost and rightmost selected points are the same (point \(1\)), so the distance is always 0. By handling this case first, the subsequent implementation can be written more simply under the assumption that \(N \geq 2\).

• Fast I/O Since \(M\) can be as large as \(5 \times 10^5\), in Python you can significantly reduce execution time by reading all input at once using sys.stdin.read().split().

  Source Code

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # N = 1 の場合は、最も左と最も右が同じポイントになるため距離は 0
    if N == 1:
        print(0)
        return
        
    D = [int(x) for x in input_data[3:]]
    
    # 各ポイントの座標を計算
    X = [0] * M
    for i in range(M - 1):
        X[i+1] = X[i] + D[i]
        
    # 尺取り法を用いて、隣接距離 K 以上で N 個のポイントを選べるか判定
    curr_idx = 0
    next_idx = 0
    for _ in range(N - 1):
        target = X[curr_idx] + K
        while next_idx < M and X[next_idx] < target:
            next_idx += 1
        if next_idx == M:
            print(-1)
            return
        curr_idx = next_idx
        
    # 条件を満たす選び方が存在する場合、最大距離は常に全体の端から端までの距離となる
    print(X[M-1])

if __name__ == '__main__':
    solve()

---

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