Submission #2546371

---

Source Code Expand

#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

int n;
const int INF = 1e9;

struct Circle {
	int lb;
	int ub;

	bool operator< (const Circle &o) const {
		return ub == o.ub ? lb > o.lb : ub < o.ub;
	}
};

int main() {
	cin >> n;
	vector <Circle> circle(n);
	rep (i, n) {
		int x, r;
		cin >> x >> r;
		circle[i].lb = x - r;
		circle[i].ub = x + r;
	}

	rep (i, n) circle[i].lb *= -1;
	sort(circle.begin(), circle.end());

	vector <int> dp(n, INF);
	rep (i, n) {
		*lower_bound(dp.begin(), dp.end(), circle[i].lb) = circle[i].lb;
	}

	cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin() << endl;
	return 0;
}

Submission Info

Judge Result