Overview

The positions where a base station can transmit signals to resident \(i\) can be represented as the interval \([X_i - R_i, X_i + R_i]\). By restricting the candidate positions for base stations to the right endpoints of each interval and adopting the policy of “counting each interval only at the first base station that covers it”, this problem can be solved in \(O(K N^2)\) time by combining precomputation using the 2D imos method and dynamic programming (DP).

Analysis

1. Rephrasing the Problem in Terms of Intervals

The condition for resident \(i\) to receive signals from a base station at coordinate \(P\) is \(|X_i - P| \le R_i\). This is equivalent to the base station’s coordinate \(P\) being contained within the closed interval \([X_i - R_i, X_i + R_i]\). Hereafter, let \(L_i = X_i - R_i,\ R'_i = X_i + R_i\).

2. Narrowing Down Candidate Base Station Positions

Although base stations can be placed anywhere on the real line, we can see that in an optimal solution, base station positions can be restricted to match the right endpoint of some interval \(R'_i\). This is because, when sliding a base station to the right, a resident ceases to be covered only at the moment when the station passes the right endpoint of that resident’s interval. Therefore, without changing the set of covered residents, we can slide the base station to the right until it reaches a right endpoint.

Thus, the candidate coordinates for placing base stations are narrowed down to at most \(N\) values: \(\{R'_1, R'_2, \dots, R'_N\}\). Removing duplicates and sorting these in ascending order, let them be \(c_1 < c_2 < \dots < c_M\) (\(M \le N\)).

3. Establishing Rules to Avoid Duplicate Counting

When multiple base stations cover the same interval, that resident must be counted only once. When choosing base stations from left to right, we consider assigning each interval to the leftmost base station that covers it.

Let \(c_u\) be the previously selected base station, and let \(c_v\) (\(u < v\)) be the currently selected base station. The conditions for an interval \(i\) to be covered for the first time by base station \(c_v\) are as follows: - It is not covered by the previous base station \(c_u\) (or any base station to its left): \(c_u < L_i\) - It is covered by the current base station \(c_v\): \(L_i \le c_v \le R'_i\)

In summary, intervals satisfying \(c_u < L_i \le c_v \le R'_i\) constitute the new score gained by choosing \(c_v\) given that the previous base station was \(c_u\). Note that for the first base station chosen (the 1st one), there is no previous base station; by introducing a sentinel \(c_0 = -\infty\), this case can be handled uniformly with the same formula.

Algorithm

1. Extracting Candidate Points: Compute each resident’s interval \([L_i, R'_i]\), extract the unique values of \(R'_i\), and sort them as \(c_1 < \dots < c_M\). Also add the sentinel \(c_0 = -\infty\). If the number of base stations \(K\) is greater than \(M\), placing extra base stations at the same position or redundantly does not help, so set \(K \leftarrow \min(K, M)\).

2. Precomputing Costs (2D Imos Method): For each pair \((u, v)\), let cost[u][v] be the number of intervals satisfying \(c_u < L_i \le c_v \le R'_i\). Considering the range of \((u, v)\) to which a single interval \([L_i, R'_i]\) contributes:

   • Condition on \(v\): The range of \(v\) satisfying \(L_i \le c_v \le R'_i\) can be found via binary search as \([v_{\text{start}}, v_{\text{end}}]\).
   • Condition on \(u\): The maximum \(u\) satisfying \(c_u < L_i\) is \(u_{\text{max}} = v_{\text{start}} - 1\), so \(0 \le u \le u_{\text{max}}\).

This corresponds to a \(+1\) addition to the rectangular region \([0, u_{\text{max}}] \times [v_{\text{start}}, v_{\text{end}}]\) on the \((u, v)\) plane. By using the 2D imos method, performing the additions for all intervals can be done in \(O(N \log M + M^2)\).

1. Dynamic Programming (DP):
   • dp[t][v]: The maximum number of residents who can receive signals when \(t\) base stations are placed and the last placed base station is \(c_v\).

Base Case: - dp[1][v] = cost[0][v] (\(1 \le v \le M\))

Transitions: For \(t = 2, 3, \dots, K\): $\(dp[t][v] = \max_{1 \le u < v} \{ dp[t-1][u] + \text{cost}[u][v] \}\)$

Answer: The answer is the maximum value of \(\max_{1 \le v \le M} dp[t][v]\) across all steps.

Complexity

• Time Complexity:
  • Extracting and sorting coordinates: \(O(N \log N)\)
  • Precomputing cost using the 2D imos method: \(O(N \log M + M^2)\)
  • DP updates: In each of the \(K\) steps, iterating \(v\) over \(1 \dots M\) and \(u\) over \(1 \dots v-1\) takes \(O(K M^2)\).
  • Overall, it is \(O(K M^2) \le O(K N^2)\). Since \(N \le 250\), we have \(K N^2 \le 250^3 \approx 1.56 \times 10^7\), which easily runs well within the time limit.
• Space Complexity:
  • Storing the cost array and DP table consumes \(O(M^2) \le O(N^2)\) memory, which is negligible for \(N \le 250\).

Implementation Notes

• 2D Imos Method: Naively computing cost[u][v] with a loop for each interval would take \(O(N M^2)\), but using the imos method by exploiting the fact that it is a rectangular addition optimizes it to \(O(N \log M + M^2)\).

• Improving Cache Efficiency: In the DP transition dp[u] + cost[u][v], since \(v\) is fixed and \(u\) varies, the first index of the 2D array cost[u][v] changes. In languages like Python, transposing cost beforehand so that cost_T[v][u] = cost[u][v] improves memory locality; accesses in the inner loop become contiguous, which significantly reduces execution time.

  Source Code

import sys
from bisect import bisect_left, bisect_right


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

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

    intervals = []
    idx = 2
    R_primes = []
    for _ in range(N):
        x = int(input_data[idx])
        r = int(input_data[idx + 1])
        idx += 2
        L = x - r
        R = x + r
        intervals.append((L, R))
        R_primes.append(R)

    c_unique = sorted(list(set(R_primes)))
    M = len(c_unique)
    K = min(K, M)

    c = [-10**18] + c_unique

    # 2次元いもす法で cost[u][v] を前計算
    # cost[u][v]: c_u < L_i <= c_v <= R_i を満たす区間の数 (0 <= u < v <= M)
    diff = [[0] * (M + 2) for _ in range(M + 2)]

    for L, R in intervals:
        v_start = bisect_left(c, L)
        if v_start > M:
            continue
        v_end = bisect_right(c, R) - 1
        if v_start > v_end:
            continue
        u_max = v_start - 1

        diff[0][v_start] += 1
        diff[0][v_end + 1] -= 1
        diff[u_max + 1][v_start] -= 1
        diff[u_max + 1][v_end + 1] += 1

    for u in range(M + 1):
        row = diff[u]
        for v in range(1, M + 1):
            row[v] += row[v - 1]

    for u in range(1, M + 1):
        row_prev = diff[u - 1]
        row_curr = diff[u]
        for v in range(M + 1):
            row_curr[v] += row_prev[v]

    cost = diff

    # 転置してメモリアクセスを高速化
    cost_T = [[cost[u][v] for u in range(v)] for v in range(M + 1)]

    dp = [cost[0][v] for v in range(M + 1)]
    ans = max(dp[1:])

    for t in range(2, K + 1):
        next_dp = [0] * (M + 1)
        for v in range(1, M + 1):
            c_v = cost_T[v]
            m = 0
            for u in range(1, v):
                val = dp[u] + c_v[u]
                if val > m:
                    m = val
            next_dp[v] = m
        dp = next_dp
        cur_max = max(dp[1:])
        if cur_max > ans:
            ans = cur_max

    print(ans)


if __name__ == "__main__":
    main()

---

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