Overview

This problem asks for the minimum cost to cover all \(N\) houses arranged on a straight line by installing some number of streetlights chosen from \(M\) available types.

Analysis

1. Sorting Houses and Dividing into Intervals

The houses are scattered on a number line. To make them easier to handle, we first sort the house coordinates in ascending order: \(X_1 < X_2 < \dots < X_N\).

When covering all houses, the set of houses covered by a single streetlight forms a contiguous subsequence (interval) among the sorted houses. For example, if a streetlight covers house \(j+1\) and house \(i\) (\(j+1 < i\)), then all houses \(j+2, \dots, i-1\) between them must also fall within the range of that same streetlight. Therefore, this problem can be reduced to “partitioning all houses into several contiguous intervals, and covering each interval with a single streetlight.”

2. Condition for Covering a Single Interval

Consider covering the interval from house \(j+1\) to house \(i\) (\(X_{j+1}, \dots, X_i\)) with a single streetlight. The distance between the endpoints of this interval is \(D = X_i - X_{j+1}\). A streetlight with radius \(R\) can cover an interval of length at most \(2R\) by choosing an appropriate placement (placing it exactly at the center of the interval). Therefore, any streetlight with diameter \(2R \ge D\) can cover all houses in this interval with a single streetlight.

3. Applying Dynamic Programming (DP)

Define \(dp[i]\) as “the minimum cost to cover the first \(i\) houses.” To compute \(dp[i]\), we exhaustively search over all possible last intervals “from house \(j+1\) to house \(i\)” (\(0 \le j < i\)). The following recurrence relation holds:

\[dp[i] = \min_{0 \le j < i} \left( dp[j] + (\text{minimum cost of a streetlight with diameter at least } X_i - X_{j+1}) \right)\]

4. Fast Retrieval of the Optimal Streetlight

For each transition, we need to quickly find “the minimum cost of a streetlight with diameter at least \(D\).” We pre-sort the streetlights in ascending order of diameter \(2R\), and for each streetlight, precompute “the minimum cost among all streetlights with diameter greater than or equal to its own” as a suffix minimum (Suffix Min).

When decreasing \(j\) from \(i-1\) down to \(0\), the required diameter \(D = X_i - X_{j+1}\) monotonically increases. By exploiting this property, we advance a pointer \(k\) from left to right in a two-pointer fashion, allowing us to find the optimal streetlight for each transition in amortized \(O(1)\) time.

Algorithm

1. Sort the house coordinates \(X\) in ascending order.
2. Sort the streetlight information as pairs (diameter \(2R_j\), cost \(C_j\)) in ascending order of diameter.
3. Build the suffix minimum array suffix_min from the back of the streetlight costs.
   • suffix_min[j] represents the minimum cost among all streetlights from the \(j\)-th onward (after sorting).
4. Initialize the DP table dp with infinity (\(INF\)), and set dp[0] = 0.
5. Loop \(i\) from \(1\) to \(N\):
   • Set pointer \(k = 0\).
   • Loop \(j\) from \(i-1\) down to \(0\) in reverse order:
     • Compute the required diameter \(D = X_i - X_{j+1}\).
     • While the streetlight’s diameter is less than \(D\) (S[k].first < D), advance pointer \(k\).
     • The minimum cost among streetlights satisfying diameter \(\ge D\) is suffix_min[k].
     • Update with dp[i] = min(dp[i], dp[j] + suffix_min[k]).
6. Output dp[N], the minimum cost to cover all houses.

Complexity

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

  • Sorting houses takes \(O(N \log N)\), and sorting streetlights takes \(O(M \log M)\).
  • In the DP transitions, the outer loop runs \(N\) times, and the inner loop runs \(N\) times. For each loop iteration of \(i\), the pointer \(k\) increases at most \(M\) times, so the total processing within the inner loop (including pointer movement) is \(O(N^2 + NM)\).
  • Since \(N, M \le 3000\), the total number of operations is at most approximately \(1.8 \times 10^7\), which comfortably fits within the time limit.

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

  • This is the memory needed to store the house coordinates, streetlight data, DP table, and suffix minimum array.

Implementation Notes

• Monotonicity of pointer \(k\): When decreasing \(j\) from \(i-1\) down to \(0\) in the inner loop (expanding the covered interval to the left), the required diameter \(D = X_i - X_{j+1}\) always increases. Because of this, we only need to move pointer \(k\) to the right to find the optimal streetlight, eliminating the need for binary search.

• Overflow caution: Since the total cost and coordinate differences can exceed \(10^9\), use 64-bit integer types (C++ long long) for the DP table, suffix minimum values, and distance calculations.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> X(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> X[i];
    }
    // 家の座標を昇順にソート
    sort(X.begin() + 1, X.end());

    // 街灯の情報を格納 (2 * R_j, C_j)
    vector<pair<long long, long long>> S(M);
    for (int j = 0; j < M; ++j) {
        long long R, C;
        cin >> R >> C;
        S[j] = {2 * R, C};
    }
    // 直径(2*R)の昇順にソート
    sort(S.begin(), S.end());

    // suffix_min[j] : インデックス j 以降の街灯における最小コスト
    vector<long long> suffix_min(M + 1, INF);
    for (int j = M - 1; j >= 0; --j) {
        suffix_min[j] = min(suffix_min[j + 1], S[j].second);
    }

    // dp[i] : 最初の i 軒の家をすべてカバーするための最小コスト
    vector<long long> dp(N + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= N; ++i) {
        int k = 0;
        for (int j = i - 1; j >= 0; --j) {
            long long D = X[i] - X[j + 1];
            // 直径 D 以上の街灯を探す
            while (k < M && S[k].first < D) {
                k++;
            }
            long long cost = (k < M) ? suffix_min[k] : INF;
            if (cost != INF && dp[j] != INF) {
                dp[i] = min(dp[i], dp[j] + cost);
            }
        }
    }

    cout << dp[N] << "\n";

    return 0;
}

---

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