Overview

This problem asks us to select 2 or more locations from several candidate sites on a coordinate line such that the distance between every pair of adjacent selected sites is at most \(D\), while minimizing the total construction cost.

By sorting in ascending order of coordinates and combining Dynamic Programming (DP) with a Sliding Minimum (Monotonic Queue), we can efficiently find the optimal selection.

---

Analysis

1. Sorting by Coordinates and DP Design

We consider selecting relay stations from left to right. First, we sort the candidate sites in ascending order of their coordinates \(X_i\).

For the \(i\)-th site after sorting, we define a DP that manages the following two values: - \(dp[i]\): The minimum total construction cost when site \(i\) is selected as the 2nd or later relay station. - \(V[i]\): The minimum total construction cost when site \(i\) is selected as the 1st, 2nd, or later relay station.

Since the cost of selecting site \(i\) as the first candidate site is \(C_i\), we can express this as: $\(V[i] = \min(dp[i], C_i)\)$

2. State Transitions

When selecting site \(i\) as the 2nd or later relay station, let \(j\) (\(j < i\)) be the previously selected relay station. Since the distance between adjacent relay stations must be at most \(D\), we need \(X_i - X_j \leq D\).

Therefore, \(dp[i]\) can be updated as follows: $\(dp[i] = C_i + \min_{j: X_i - X_j \leq D} V[j]\)$

3. Need for Optimization

If we naively search through all \(j\) satisfying the condition for each \(i\), the worst-case time complexity would be \(O(N^2)\), which would exceed the time limit (TLE) under the constraint \(N \leq 2 \times 10^5\).

Here, let us focus on the search range \(\{j \mid X_i - X_j \leq D\}\). As \(i\) advances, the range (window) of \(j\) satisfying the condition slides to the right. To efficiently find the “minimum value within a sliding window,” we use the Sliding Minimum (Monotonic Queue) technique. By using a double-ended queue (deque), we can always retrieve the minimum value within the window in \(O(1)\) time.

---

Algorithm

The specific procedure using the sliding minimum is as follows:

1. Initialization:

   • Sort the candidate sites in ascending order of coordinates \(X_i\).
   • Initialize the \(dp\) array with infinity (inf).
   • Prepare a double-ended queue deq for managing the minimum value. deq stores indices and is maintained so that the corresponding \(V\) values are in ascending order (the front always holds the minimum).

2. Transitions (loop from left to right, \(i = 0, 1, \ldots, N-1\)):

   • Window update (removing from the left end): Remove sites whose distance from the current site \(i\) exceeds \(D\) (i.e., \(j\) where \(X_i - X_j > D\)) from the left end of the window. If the index at the front of the queue satisfies this condition, remove it from the queue.
   • Updating \(dp[i]\): If the queue is not empty, the index \(j = \text{deq}[0]\) at the front of the queue gives the minimum value of \(V[j]\) within the window. Using this, we update \(dp[i] = C_i + V[j]\). If the queue is empty, there is no relay station that can be placed immediately before, so \(dp[i] = \infty\) remains.
   • Updating \(V[i]\): Compute \(V[i] = \min(dp[i], C_i)\).
   • Queue maintenance (adding to the right end): Add the newly obtained \(V[i]\) to the queue. At this point, any elements at the back of the queue with values greater than or equal to \(V[i]\) will never be selected as the minimum in the future, so they are all removed from the queue (maintaining monotonicity). Then, add \(i\) to the back of the queue.

3. Output the answer:

   • The minimum value of \(dp[i]\) across all sites is the answer. If the minimum value remains infinity (inf), then no valid selection exists, and we output -1.

---

Complexity

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

  • Sorting the candidate sites takes \(O(N \log N)\).
  • In the DP transitions, each index \(i\) is added to the queue at most once and removed at most once. Therefore, the total time for queue operations is \(O(N)\), and the overall complexity is \(O(N \log N)\) with sorting as the bottleneck.

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

  • The list of candidate sites, the DP table, and the queue each use \(O(N)\) memory.

---

Implementation Notes

• Handling the “2 or more locations” condition: \(dp[i]\) stores the “minimum cost when selected as the 2nd or later station,” and the cost \(C_i\) for selecting it only as the first candidate is not included in \(dp[i]\). This way, simply taking \(\min(dp)\) at the end correctly gives us the minimum cost for the case where “2 or more locations are selected.”

• Contents of the sliding minimum queue: The queue stores indices \(j\) rather than the values of \(V[j]\) themselves. This allows us to directly perform the coordinate distance check (\(X_i - X_j > D\)) from the indices.

  Source Code

import sys
from collections import deque


def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    D = int(input_data[1])

    # 座標と建設費用をペアにして格納
    points = []
    idx = 2
    for _ in range(N):
        points.append((int(input_data[idx]), int(input_data[idx + 1])))
        idx += 2

    # 座標の昇順にソート
    points.sort(key=lambda x: x[0])

    dp = [float("inf")] * N
    V = [0] * N

    deq = deque()
    L = 0

    for i in range(N):
        X_i, C_i = points[i]

        # 距離が D より大きい左端の要素をウィンドウから除外
        while L < i and X_i - points[L][0] > D:
            if deq and deq[0] == L:
                deq.popleft()
            L += 1

        # ウィンドウ内に要素が存在する場合、最小値を使って dp[i] を更新
        if deq:
            dp[i] = C_i + V[deq[0]]
        else:
            dp[i] = float("inf")

        V[i] = min(dp[i], C_i)

        # モノトニックキューの維持
        while deq and V[deq[-1]] >= V[i]:
            deq.pop()
        deq.append(i)

    ans = min(dp)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    solve()

---

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