Overview

This problem asks for the minimum cost to cover all \(N\) houses placed on a number line, using some street lights with coverage range \(2R_j\) and cost \(C_j\). Street lights can be placed at any position freely, and the same type of street light can be used multiple times.

---

Analysis

1. Organizing the Properties of Street Lights

When street light \(j\) is placed at some coordinate, the length (diameter) of the range it can cover is \(D_j = 2R_j\). Therefore, each street light can be viewed as “an item that can cover an interval of length \(D_j\) at cost \(C_j\)”.

Now, let’s compare the following two street lights \(A\) and \(B\): - Street light \(A\): coverage range \(D_A\), cost \(C_A\) - Street light \(B\): coverage range \(D_B\), cost \(C_B\)

If \(D_A \ge D_B\) and \(C_A \le C_B\), then there is absolutely no benefit to using street light \(B\) (since street light \(A\) covers a wider range at a lower cost). By removing such “useless street lights” in advance (filtering), we can organize the remaining list of street lights into a clean monotonically increasing relationship where “as the coverage range \(D\) increases, the cost \(C\) also increases”.

2. Applying Dynamic Programming (DP)

Sort the house coordinates in ascending order as \(X_1 < X_2 < \dots < X_N\). Consider covering houses sequentially from left to right, and define the following DP (dynamic programming):

• \(DP[i]\): the minimum cost required to cover all houses up to the \(i\)-th house from the left (\(X_i\))

To compute \(DP[i]\), we consider what range the last placed street light covers. Assume the last placed street light covers the rightmost house \(X_i\) and also covers houses up to \(X_{j+1}\) on the left (\(0 \le j < i\)).

The length of the interval this street light must cover is \(d = X_i - X_{j+1}\). Since street lights can be placed freely at any real coordinate, by aligning the right end exactly at \(X_i\), the left side is covered up to \(X_i - D\). Therefore, we should choose the street light with the lowest cost among those satisfying coverage range \(D \ge d\).

The transition formula is as follows: $\(DP[i] = \min_{0 \le j < i} \{ DP[j] + (\text{minimum street light cost that can cover length } \ge X_i - X_{j+1}) \}\)$

3. Optimization Using the Two-Pointer Technique

When trying all \(j\) (decreasing from \(i-1\) to \(0\)) for each \(i\), the required coverage length \(d = X_i - X_{j+1}\) monotonically increases as \(j\) decreases.

If the street light list is sorted in ascending order of coverage range \(D\), then as the required coverage range \(d\) increases, the minimum street light index \(k\) satisfying \(D_k \ge d\) also monotonically increases (moves to the right). Therefore, when decreasing \(j\) in the inner loop, there is no need to search for \(k\) from \(0\) each time; we can simply advance from the previous position of \(k\) (similar to the two-pointer technique). This allows transitions to be performed efficiently.

---

Algorithm

1. Initialization and Sorting:

   • Sort the house coordinates \(X\) in ascending order.
   • Set the effective coverage range of each street light as \(D_j = 2R_j\).

2. Filtering Street Lights:

   • Sort the street lights by “coverage range \(D\) in descending order, cost \(C\) in ascending order”.
   • Scan from left to right, extracting only those that update the minimum cost so far.
   • By reversing the extracted list, we obtain a waste-free street light list filtered where both \(D\) and \(C\) are in ascending order.

3. DP Transitions:

   • Prepare a \(DP\) array of size \(N+1\), initialized with a sufficiently large value (\(\infty\)), with \(DP[0] = 0\).
   • Advance \(i\) from \(1\) to \(N\).
     • Set the street light list pointer \(k = 0\).
     • Loop \(j\) in reverse order (decrement) from \(i-1\) to \(0\).
     • Compute the required length \(d = X_{i-1} - X_j\) (since it’s 0-indexed, house \(i\) corresponds to X[i-1] and house \(j+1\) corresponds to X[j]).
     • Advance pointer \(k\) as long as \(D_k < d\).
     • If \(k\) exceeds the size of the street light list, no street light can cover such a long interval, so break out of the inner loop.
     • Update the value with \(DP[i] = \min(DP[i], DP[j] + C_k)\).

4. Output:

   • \(DP[N]\) is the minimum cost to cover all houses.

---

Complexity

• Time Complexity: \(O(N^2 + M \log M)\)

  • Sorting the houses takes \(O(N \log N)\).
  • Sorting and filtering the street lights takes \(O(M \log M)\).
  • In the DP computation, the outer loop runs \(N\) times and the inner loop runs up to \(N\) times. Within the inner loop, pointer \(k\) increases at most up to \(M\), so the total time for DP transitions is \(O(N^2 + M)\).
  • Therefore, the overall time complexity is \(O(N^2 + M \log M)\), which comfortably fits within the time limit.

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

  • The DP table has size \(O(N)\), and the filtered street light list has size at most \(O(M)\), so memory usage is kept very small.

---

Implementation Notes

• Street Light Filtering: This process creates a clean monotonicity between the street lights’ “coverage range \(D\)” and “cost \(C\)”, making binary search and the two-pointer technique applicable. This is one of the very powerful standard techniques in competitive programming.

• Index Correspondence: In the code, implementation uses 0-indexed arrays, so house \(i\) (1-indexed) corresponds to X[i-1]. The distance from house \(j+1\) to house \(i\) is expressed as X[i-1] - X[j].

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    X = [int(x) for x in data[2 : 2 + N]]
    X.sort()

    lights = []
    idx = 2 + N
    for _ in range(M):
        r = int(data[idx])
        c = int(data[idx + 1])
        lights.append((2 * r, c))
        idx += 2

    # 街灯のフィルタリング
    # カバー範囲Dが広いのにコストCが高いものは不要。
    # Dの降順、Cの昇順でソートし、これまでの最小コストを更新するものだけを残す。
    lights.sort(key=lambda x: (-x[0], x[1]))
    filtered = []
    min_c = float("inf")
    for d, c in lights:
        if c < min_c:
            filtered.append((d, c))
            min_c = c
    filtered.reverse()  # Dの昇順にする

    D_list = [item[0] for item in filtered]
    C_list = [item[1] for item in filtered]
    K = len(filtered)

    INF = 10**18
    DP = [INF] * (N + 1)
    DP[0] = 0

    for i in range(1, N + 1):
        xi = X[i - 1]
        k = 0
        dp_i = INF
        for j in range(i - 1, -1, -1):
            d = xi - X[j]
            while k < K and D_list[k] < d:
                k += 1
            if k == K:
                break
            val = DP[j] + C_list[k]
            if val < dp_i:
                dp_i = val
        DP[i] = dp_i

    print(DP[N])


if __name__ == "__main__":
    solve()

---

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