住民 \(i\) が基地局から電波を受信できることは、その基地局の座標が \(X _ i-R _ i\) 以上 \(X _ i+R _ i\) 以下であることと同値です。 \((X _ i-R _ i,X _ i+R _ i)\) をあらためて \((l _ i,r _ i)\) とおくことにします。

同じ座標に \(2\) つ以上の基地局があったとき、それらをまとめて \(1\) つの基地局にしても電波を受信できる住民の人数は変わりません。 よって、この問題はたかだか \(K\) 個の実数からなる集合 \(X=\lbrace x _ 1,x _ 2,\ldots,x _ k\rbrace\) を選び、\(X\cap\lbrack l _ i,r _ i\rbrack\ne\emptyset\) であるような \(i\) の個数を最大化する問題であるということができます。

\(\lbrace x _ j\rbrace\cap\lbrack l _ i,r _ i\rbrack\ne\emptyset\) であるような \(i\) が存在しない \(x _ j\) は \(X\) から取り除いても受信できる住民の人数は変わりません。 よって、すべての \(x _ j\in X\) について、座標 \(x _ j\) の基地局からいずれかの住民が電波を受信できるような最適解が存在します。

また、座標 \(x _ j\) の基地局についてその基地局から電波を受信できる住民全体を \(S _ {x _ j}\) とします（上の議論から、\(S _ {x _ j}\ne\emptyset\) としてよいです）。 \(S _ {x _ j}\) に含まれる住民の \(r _ i\) の最小値を \(m _ j\) とすると、座標 \(x _ j\) の基地局を座標 \(m _ j\) まで移動させても電波を受信できる住民の人数が減ることはありません。 よって、すべての \(x _ j\in X\) についてある住民 \(i\) が存在して \(x _ j=r _ i\) となるような最適解が存在します。

以上より、この問題は \(\lbrace r _ 1,r _ 2,\ldots,r _ N\rbrace\) からたかだか \(K\) 個の実数を選んで \(X=\lbrace x _ 1,x _ 2,\ldots,x _ k\rbrace\) とし、\(X\cap\lbrack l _ i,r _ i\rbrack\ne\emptyset\) であるような \(i\) の個数を最大化する問題であるということができます。

必要なら住民の番号を入れ替えて \(r _ 1,r _ 2,\ldots,r _ N\) は昇順に並んでいるとします。 番兵として \(r _ 0=-\infty\) を追加しておきます。

\(\operatorname{dp}[i][j]\coloneqq\lbrace r _ 1,r _ 2,\ldots,r _ i\rbrace\) のうち \(r _ i\) を含むたかだか \(j\) 個を選んだ時点で電波を受信できる住民の人数の最大値 \((1\le j\le i\le N)\) とします。 \(1\le j\le i\le N\) を満たさない \(i,j\) については便宜上 \(\operatorname{dp}[i][j]=0\) とします。 求めるものは \(\displaystyle\max _ {1\le j\le K,j\le i\le N}\operatorname{dp}[i][j]\) です。

\(c(a,b)\) を \(r _ a\notin\lbrack l _ k,r _ k\rbrack\wedge r _ b\in\lbrack l _ k,r _ k\rbrack\) を満たす \(k\) の個数 \((0\le a\le b\le N)\)とすると、この DP は以下のような漸化式で求めることができます。

\[\operatorname{dp}[i][j]=\max _ {0\le k\lt i}\bigl\lbrace\operatorname{dp}[k][j-1]+c(k,i)\bigr\rbrace\]

各 \(i,j\ (1\le j\le i\le N)\) に対して \(c(k,i)\) を愚直に求めると時間計算量が \(\Theta(N ^ 4)\) となってしまいますが、\(c(k,i)\) の値を事前にすべての \(0\le k\le i\le N\) に対して求めておくことで全体で時間計算量を \(O(N ^ 3)\) とすることができます。

また、\(j\) の昇順に処理を行い、\(\operatorname{dp}[k][j-1]+c(k,i)\) を管理することを考えると、イベントソートの要領で区間加算・区間最大値を処理すればよいことがわかります。 遅延セグメント木などを使って処理を行うことで、この問題を \(O(NK\log N)\) 時間で解くこともできます。

実装例は以下のようになります。 \(c(k,i)\) の値を前計算する実装と、遅延セグメント木を使って \(O(NK\log N)\) 時間で解く実装の両方を載せています。

前者の実装でも、\(j\) の昇順・\(i\) の降順に処理を行うことで DP を in-place に更新しています。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<pair<int, int>> interval(N);
    vector<int> right; // 右端の値の一覧
    for (auto& [l, r] : interval) {
        int X, R;
        cin >> X >> R;
        l = X - R;
        r = X + R;
        right.emplace_back(X + R);
    }
    // 番兵を追加してソート
    right.emplace_back(-2000000001);
    ranges::sort(right);

    // c(a, b) の値を前計算
    vector c(N + 1, vector<int>(N + 1));
    for (int a = 0; a <= N; ++a) {
        for (int b = 0; b <= N; ++b) {
            for (auto [l, r] : interval) {
                if (right[a] < l && l <= right[b] && right[b] <= r) {
                    ++c[a][b]; // 条件を満たす区間の個数を数える
                }
            }
        }
    }

    // j の昇順、i の降順に更新
    vector<int> dp(N + 1);
    for (int j = 0; j < K; ++j) {
        for (int i = N; i >= 0; --i) {
            int ans = 0;
            for (int k = 0; k < i; ++k) {
                ans = max(ans, dp[k] + c[k][i]);
            }
            dp[i] = ans;
        }
    }
    cout << ranges::max(dp) << endl;

    return 0;
}

N, K = map(int, input().split())

interval = []
for i in range(N):
    X, R = map(int, input().split())
    interval.append((X - R, X + R))

right = [-2000000001] + [r for l, r in interval] # 右端の値の一覧 + 番兵
right.sort() # 昇順にソート

# c(a, b) の値を前計算
c = [[0 for i in range(N + 1)] for j in range(N + 1)]
for a in range(N + 1):
    for b in range(N + 1):
        for l, r in interval:
            if right[a] < l <= right[b] <= r:
                c[a][b] += 1 # 条件を満たす区間の個数を数える

# j の昇順、i の降順に更新
dp = [0 for i in range(N + 1)]
for j in range(K):
    for i in range(N, -1, -1):
        ans = 0
        for k in range(i):
            ans = max(ans, dp[k] + c[k][i])
        dp[i] = ans

print(max(dp))

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <functional>
#include <atcoder/lazysegtree>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    // イベントソートで処理を行う
    vector<array<int, 3>> event;
    // r[i] を使って後で座標圧縮する
    vector<int> right;
    for (int i = 0; i < N; ++i) {
        int X, R;
        cin >> X >> R;
        event.emplace_back(array{X - R, 0, 0});
        event.emplace_back(array{X + R, 2, X - R});
        right.emplace_back(X + R);
    }
    // 番兵を追加してソート
    right.emplace_back(-2000000001);
    ranges::sort(right);
    right.erase(ranges::unique(right).begin(), right.end());

    // 座標圧縮
    for (auto& [time, type, value] : event) {
        time = ranges::lower_bound(right, time) - right.begin();
        if (type == 2) {
            value = ranges::lower_bound(right, value) - right.begin();
        }
    }

    int M = right.size();
    for (int i = 1; i < M; ++i) {
        event.emplace_back(array{i, 1, 0});
    }
    ranges::sort(event, greater{}); // イベントソート

    // 遅延セグメント木で区間加算・区間最大値を求める
    atcoder::lazy_segtree<int, [](int a, int b){return max(a, b);}, []{return 0;}, int, plus{}, plus{}, []{return 0;}> dp(M);
    for (int i = 0; i < K; ++i) {
        for (auto [time, type, value] : event) {
            if (type == 0) {
                dp.apply(0, time, -1);
            } else if (type == 1) {
                dp.set(time, dp.prod(0, time));
            } else {
                dp.apply(0, value, 1);
            }
        }
    }

    cout << dp.all_prod() << endl;

    return 0;
}