Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <string>
- #include <math.h>
- #include <cmath>
- #include <set>
- #include <map>
- #include <cassert>
- #include <algorithm>
- #include <ctime>
- #include <iomanip>
- #include <queue>
- using namespace std;
- #define mp make_pair
- #define sz size()
- #define all(x) x.begin(),x.end()
- #define forn(i,n) for (int i = 0; i<int(n); i++)
- #define sqr(x) ((x)*(x))
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> ii;
- const int INF = 1e9 + 7;
- const ld EPS = 1e-14;
- struct set_compare {
- bool operator() (const pair<ll, int> a, const pair<ll, int> b) const{
- return (a.first>b.first || a.first == b.first && a.second > b.second);
- }
- };
- const int NUM = 100007;
- ll dp[NUM][3] = { 0 };
- void init(){
- for (int i = 0; i < NUM; i++){
- for (int j = 0; j < 3; j++){
- dp[i][j] = 0;
- }
- }
- }
- vector<ll> xs;
- vector<ll> xs1;
- vector<ll> hs;
- const ll INF_THIS = -1000008;
- int find_ind(ll x){
- auto it = upper_bound(all(xs), x);
- if (it == xs.end())
- return -1;
- else
- return (int)(it-xs.begin());
- }
- int find_ind1(ll x){
- auto it = upper_bound(all(xs1), x);
- if (it == xs1.end())
- return -1;
- else
- return (int)(it - xs1.begin());
- }
- //#define DEBUG
- int main(){
- #ifdef DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- init();
- int n;
- cin >> n;
- xs.resize(n);
- hs.resize(n);
- xs1.resize(n);
- for (int i = 0; i < xs.size(); i++){
- cin >> xs[i] >> hs[i];
- xs1[i] = xs[i] - hs[i];
- if (i>0 && xs[i] - hs[i] <= xs[i - 1])
- dp[i][1] = INF_THIS;
- }
- for (int i = 0; i < n - 1; i++){
- if (xs[i] + hs[i] >= xs[i + 1])
- dp[i][2] = INF_THIS;
- }
- for (int i = n - 1; i >= 0; i--){
- if (dp[i][0] == 0){
- if (i + 1 < n) dp[i][0] = max(dp[i + 1][0], dp[i + 1][2]);
- else
- dp[i][0] = 0;
- int ind1 = find_ind1(xs[i]);
- if (ind1 != -1 && dp[ind1][1]>=0) dp[i][0] = max(dp[i][0], dp[ind1][1]);
- dp[i][0] = max(dp[i][0], 0ll);
- }
- if (dp[i][1] == 0){
- if (i + 1 < n) dp[i][1] = max(dp[i + 1][0], dp[i + 1][2]) + 1;
- else
- dp[i][1] = 1;
- int ind1 = find_ind1(xs[i]);
- if (ind1 != -1 && dp[ind1][1]>=0) dp[i][1] = max(dp[i][1], dp[ind1][1] + 1);
- dp[i][1] = max(dp[i][1], 1ll);
- }
- if (dp[i][2] == 0){
- int ind1 = find_ind(xs[i] + hs[i]);
- if (ind1 != -1)
- dp[i][2] = max(dp[ind1][0], dp[ind1][2]) + 1;
- else
- dp[i][2] = 1;
- ind1 = find_ind1(xs[i] + hs[i]);
- if (ind1 != -1 && dp[ind1][1]>=0) dp[i][2] = max(dp[i][2], dp[ind1][1] + 1);
- dp[i][2] = max(dp[i][2], 1ll);
- }
- }
- ll ans = 0;
- ans = max(ans, dp[0][0]);
- ans = max(ans, dp[0][1]);
- ans = max(ans, dp[0][2]);
- //if (ans == 1) while (true);
- cout << ans;
- #ifdef DEBUG
- cerr << "Time elapsed: " << (ld)clock() / CLOCKS_PER_SEC << " sec." << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement