Overview

Sort the house coordinates in ascending order, and starting from “the leftmost house not yet illuminated,” consider only optimal transitions when placing streetlights. Use dynamic programming to find the minimum cost.

Analysis

Key Insight

Let the houses be ordered by coordinate as \(x_0 < x_1 < \dots < x_{N-1}\).
Suppose the leftmost uncovered house is \(x_i\), and we place a streetlight with radius \(R\) “so that it illuminates \(x_i\).” If we want to illuminate as many houses to the right as possible, it is optimal to place the center of the streetlight at \(x_i + R\).

• If the center is placed at \(p\), the illuminated interval is \([p-R,\; p+R]\)
• To illuminate \(x_i\), we need \(p \in [x_i-R,\; x_i+R]\)
• To maximize the right endpoint \(p+R\), set \(p=x_i+R\)
• Therefore, the illuminated interval is \([x_i,\; x_i+2R]\)

In other words, “the range of houses that can be illuminated next” is uniquely determined by \(x_i\) and the streetlight type alone.

Why the Naive Solution is Difficult

• “Where to place the streetlight” involves real-valued coordinates, so the search space is infinite
• Binary searching at each state gives \(O(NM\log N)\), which tends to be too slow for \(N,M\le 3000\)

How to Solve This

1. Reduce the real-valued placement problem to just “how far to the right can we reach from the leftmost uncovered house \(x_i\)” (using the insight above).
2. Among streetlights with the same reach distance \(2R\), keep only the cheapest cost.
3. Furthermore, if there exists a streetlight \((L', C')\) with \(L' \ge L\) and \(C' \le C\) for some streetlight \((L, C)\), then \((L,C)\) is always inferior, so remove it (elimination of dominated types).
4. Speed up the DP transition by using per-type pointers to find “the last house at or before \(x_i+L\)” (the right endpoint is monotonically increasing for each type).

Here, by setting \(L=2R\), the right endpoint becomes \(x_i+L\), which can be handled as an integer.

Algorithm

1. Preprocessing (Compression and Elimination of Streetlight Types)

• For each streetlight, compute \(L=2R\), and among those with the same \(L\), keep only the one with minimum \(C\).
• Sort the remaining \((L,C)\) pairs in ascending order of \(L\).
• Scan from right to left, keeping only those cheaper than the running minimum cost minC.
  • If there exists a cheaper option on the right side (larger \(L\)), then the left side is never useful.

2. DP (Covering Houses from Left to Right)

• dp[i] = “the minimum cost to illuminate all \(i\) houses from the left (\(x_0 \sim x_{i-1}\))”
• Initial value: dp[0]=0, all others are INF
• From state \(i\) (the next house to illuminate is \(x_i\)), place one streetlight of each type \((L,C)\):
  • That streetlight illuminates the interval \([x_i,\; x_i+L]\) (from the analysis above)
  • Therefore, it can cover all houses up to the maximum \(k\) satisfying \(x_k \le x_i+L\)
  • The next state is dp[k] = min(dp[k], dp[i] + C)

Finding the Reached Position \(k\) (Pointers)

For each type, maintain a pointer r[j] indicating “the number of houses with coordinate at most \(x_i+L\).”
As \(i\) increases, \(x_i\) also increases, so \(x_i+L\) is monotonically increasing, and r[j] only moves forward.
Therefore, simply advancing with a while loop results in at most \(N\) total movements per type.

The final answer is dp[N].

Complexity

• Time complexity:
  
  • Sorting houses: \(O(N\log N)\)
    
  • Organizing streetlight types (sorting): \(O(M\log M)\)
    
  • DP part: \(O(NK)\) (\(K\) is the number of types after dominance elimination, \(K\le M\))
  • Overall: \(O(N\log N + M\log M + NK)\)
• Space complexity: \(O(N+K)\)

Implementation Notes

• Use \(L=2R\) to handle “right endpoint \(x_i+L\)” as integers (no floating point needed).

• Among streetlights with the same \(L\), keep only the cheapest (dictionary best_by_L).

• When a streetlight with “larger range and cheaper cost” exists, streetlights with smaller range are unnecessary, so perform dominance elimination by scanning from the right.

• Instead of binary searching at each DP step, use per-type pointers r[j] for speedup.

• Since the answer can accumulate to the order of \(10^9\), set INF to a sufficiently large value (e.g., \(10^{30}\)).

  Source Code

import sys

def main() -> None:
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))
    xs = [int(next(it)) for _ in range(N)]
    xs.sort()

    best_by_L = {}
    for _ in range(M):
        R = int(next(it))
        C = int(next(it))
        L = R << 1
        prev = best_by_L.get(L)
        if prev is None or C < prev:
            best_by_L[L] = C

    items = sorted(best_by_L.items())  # (L, C) ascending by L

    # Remove dominated types: if there exists L' >= L with cost <= C, then (L,C) is useless.
    filtered = []
    minC = 10**30
    for L, C in reversed(items):
        if C < minC:
            filtered.append((L, C))
            minC = C
    filtered.reverse()

    Ls = [p[0] for p in filtered]
    Cs = [p[1] for p in filtered]
    K = len(Ls)

    INF = 10**30
    dp = [INF] * (N + 1)
    dp[0] = 0

    r = [0] * K  # pointers for each type (upper_bound index)

    xs_local = xs
    dp_local = dp
    N_local = N
    for i in range(N_local):
        base = dp_local[i]
        if base == INF:
            continue
        xi = xs_local[i]
        for j in range(K):
            t = xi + Ls[j]
            rj = r[j]
            while rj < N_local and xs_local[rj] <= t:
                rj += 1
            r[j] = rj
            cand = base + Cs[j]
            if cand < dp_local[rj]:
                dp_local[rj] = cand

    print(dp_local[N_local])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.