Overview

By considering the range in which resident \(i\) can receive radio signals as the interval \([X_i - R_i, X_i + R_i]\), this problem can be rephrased as: “Choose \(K\) points on the number line to maximize the number of intervals covered by the chosen points.”

Noticing that the optimal coordinates to place base stations can be restricted to the right endpoints of the intervals, and that double-counting can be avoided by assigning each interval to the “first base station that covers it”, the problem can be solved efficiently using dynamic programming (DP) in \(O(N^3 + K N^2)\).

---

Analysis

1. Rephrasing the Problem

The condition for resident \(i\) to receive signals from a base station at coordinate \(P\) is: $\(|X_i - P| \le R_i \iff X_i - R_i \le P \le X_i + R_i\)\( Letting the left endpoint of the interval be \)L_i = X_i - R_i\( and the right endpoint be \)R_i’ = X_i + R_i\(, each resident corresponds to an interval \)[L_i, R_i’]\(. The problem becomes: "Choose \)K\( coordinates \)P_1, P_2, \dots, P_K\( to maximize the number of intervals containing at least one \)P_j$.”

2. Narrowing Down Candidate Locations for Base Stations

Although base stations can be placed anywhere on the real line, we can reduce the candidate positions to a finite set. Consider moving a base station \(P\) to the right (in the positive direction). As \(P\) moves right, it may cross the left endpoints of new intervals and thus cover more residents, but no resident will lose coverage until \(P\) passes the right endpoint of an interval it currently covers. Therefore, we never lose coverage by shifting each base station to the right until it aligns with the right endpoint \(R_i'\) of one of the intervals it covers.

Hence, it is sufficient to consider at most \(N\) candidate positions: \(\{R_1', R_2', \dots, R_N'\}\).

3. How to Avoid Double-Counting

When placing base stations in increasing order from left to right as \(P_1 < P_2 < \dots < P_k\), multiple base stations may cover the same interval. Simply summing the number of intervals covered by each base station would lead to double-counting. To prevent this, we adopt the rule of assigning each interval only to the leftmost (first) base station that covers it.

The necessary and sufficient conditions for interval \(i\) to be covered for the first time by base station \(P_m\) are: 1. It is not covered by the preceding base station \(P_{m-1}\): \(P_{m-1} < L_i\) (Since the base stations are sorted in ascending order, if the left endpoint \(L_i\) is to the right of the previous base station, the interval cannot be covered by any earlier base stations either.) 2. It is covered by base station \(P_m\): \(L_i \le P_m \le R_i'\)

In summary: $\(P_{m-1} < L_i \le P_m \le R_i'\)\( (where we define \)P0 = -\infty\(). The intervals satisfying this condition depend only on two points: the previous base station \)P{m-1}\( and the current base station \)P_m$. This allows us to formulate a dynamic programming approach that depends only on the immediately preceding state.

---

Algorithm

1. Interval Calculation and Coordinate Compression: For each resident, calculate \(L_i = X_i - R_i\) and \(R_i' = X_i + R_i\). Sort the set of candidate right endpoints \(\{R_1', \dots, R_N'\}\) and remove duplicates to obtain \(c_1 < c_2 < \dots < c_M\) (\(M \le N\)). Also, introduce a sentinel \(c_0 = -\infty\).

2. Precomputing Transition Costs: Precompute \(w[u][v]\), the number of newly covered intervals when the previous chosen base station is \(c_u\) and the next chosen base station is \(c_v\) (\(0 \le u < v \le M\)): $\(w[u][v] = \#\{ i \mid c_u < L_i \le c_v \le R_i' \}\)$

3. Dynamic Programming (DP):

   • State: \(dp[k][j] :=\) the maximum number of intervals that can be covered by placing \(k\) base stations such that the last base station is at \(c_j\).
   • Base Case: \(dp[1][j] = w[0][j] \quad (1 \le j \le M)\)
   • Transitions: For \(k = 2, 3, \dots, \min(K, M)\): $\(dp[k][j] = \max_{1 \le p < j} \{ dp[k-1][p] + w[p][j] \} \quad (1 \le j \le M)\)$

4. Computing the Final Answer: Output the maximum value of \(dp[k][j]\) over all \(k \in [1, \min(K, M)]\) and \(j \in [1, M]\).

---

Complexity

• Time Complexity:

  • Sorting and deduplicating coordinates: \(O(N \log N)\)
  • Precomputation (\(w[u][v]\)): There are \(O(M^2)\) pairs of \((u, v)\), and checking all \(N\) intervals for each pair takes \(O(N \cdot M^2) \le O(N^3)\)
  • DP transitions: The outer loop for \(k\) runs \(O(K)\) times, and the nested loops for \(j\) and \(p\) run \(O(M^2)\) times, taking \(O(K M^2) \le O(K N^2)\)
  • Overall, the time complexity is \(O(N^3 + K N^2)\). Since \(N \le 250\), \(N^3 \approx 1.5 \times 10^7\), which easily runs within the time limit.

• Space Complexity:

  • The table \(w\) requires \(O(M^2) \le O(N^2)\) space, and the DP table requires \(O(K M) \le O(K N)\) space. Thus, the total space complexity is \(O(N^2 + K N)\), which easily satisfies the memory limit.

---

Implementation Notes

• Cases where \(K > M\): The number of base stations to place, \(K\), may be greater than \(M\), the number of valid candidate locations. Since placing multiple base stations at the exact same coordinate does not cover any additional intervals, we can cap the number of base stations at \(K' = \min(K, M)\).

• Preventing Overflow: Since coordinates \(X_i\) and radii \(R_i\) can be up to \(10^9\), \(X_i \pm R_i\) can slightly exceed the range of a 32-bit signed integer (around \(\pm 2 \times 10^9\)). Use a 64-bit integer type (such as long long in C++) for coordinate calculations, including the sentinel value \(-\infty\) (e.g., \(-4 \times 10^{18}\)).

  Source Code

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<long long> L(N), R(N);
    vector<long long> c;
    for (int i = 0; i < N; ++i) {
        long long x, r;
        cin >> x >> r;
        L[i] = x - r;
        R[i] = x + r;
        c.push_back(R[i]);
    }

    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());

    int M = c.size();
    vector<long long> c_pts(M + 1);
    for (int i = 0; i < M; ++i) {
        c_pts[i + 1] = c[i];
    }

    const long long INF = 4e18;
    vector<vector<int>> w(M + 1, vector<int>(M + 1, 0));
    for (int u = 0; u <= M; ++u) {
        long long cu = (u == 0 ? -INF : c_pts[u]);
        for (int v = u + 1; v <= M; ++v) {
            long long cv = c_pts[v];
            int cnt = 0;
            for (int i = 0; i < N; ++i) {
                if (cu < L[i] && L[i] <= cv && cv <= R[i]) {
                    cnt++;
                }
            }
            w[u][v] = cnt;
        }
    }

    int K_prime = min(K, M);
    vector<vector<int>> dp(K_prime + 1, vector<int>(M + 1, 0));

    for (int j = 1; j <= M; ++j) {
        dp[1][j] = w[0][j];
    }

    for (int k = 2; k <= K_prime; ++k) {
        for (int j = 1; j <= M; ++j) {
            int mx = 0;
            for (int p = 1; p < j; ++p) {
                mx = max(mx, dp[k - 1][p] + w[p][j]);
            }
            dp[k][j] = mx;
        }
    }

    int ans = 0;
    for (int k = 1; k <= K_prime; ++k) {
        for (int j = 1; j <= M; ++j) {
            ans = max(ans, dp[k][j]);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.