区間スケジューリング問題そのものだった！！！
...とはいえ 200 点というのは衝撃！！！

問題概要

ある工場では、数直線上に $N$ 個のロボットが設置されている。ロボット $i$ は座標 $X_{i}$ に設置されていて、左右に長さ $L_{i}$ のアームを伸ばしている。

これらのロボットのうちいくつかを取り除き、残ったどの 2 つのロボットについても、アームが共通部分を持たないようにしたい。取り除かずに残せるロボットの個数の最大値を求めよ。

制約

$1 \le N \le 10^{5}$

考えたこと

つまり、以下の $N$ 個の区間についての、区間スケジューリング問題 (蟻本参照) ということになる。

$(X_{0} - L_{0}, X_{0} + L_{0})$
$(X_{1} - L_{1}, X_{1} + L_{1})$
...
$(X_{N-1} - L_{N-1}, X_{N-1} + L_{N-1})$

区間スケジューリング問題とは、いくつかの区間の中から、重ならないように最大で何個選べるかを問う問題である。

区間スケジューリング問題の解き方

区間を「終端が早い順」にソートして、とれる順にとる Greedy で解くことができる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pll = pair<long long, long long>;

int main() {
    int N; cin >> N;
    vector<pll> v(N);
    for (int i = 0; i < N; ++i) {
        long long a, l;
        cin >> a >> l;
        v[i] = {a - l, a + l};
    }

    // 区間を右端の小さい順にソート
    sort(v.begin(), v.end(), [](pll a, pll b) {
            return a.second < b.second;});

    // cur := 現在選んでいる区間のうち、最も右にあるやつの右端
    int res = 0;
    long long cur = -(1LL<<60);
    for (int i = 0; i < N; ++i) {
        if (cur > v[i].first) continue; // 被るやつは飛ばす
        ++res;
        cur = v[i].second;
    }
    cout << res << endl;
}