Guest User

Untitled

a guest
May 19th, 2015
276
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <fstream>
  4. #include <vector>
  5. #include <string>
  6. #include <math.h>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. #include <cassert>
  11. #include <algorithm>
  12. #include <ctime>
  13. #include <iomanip>
  14. #include <queue>
  15.  
  16. using namespace std;
  17.  
  18. #define mp make_pair
  19. #define sz size()
  20. #define all(x) x.begin(),x.end()
  21. #define forn(i,n) for (int i = 0; i<int(n); i++)
  22. #define sqr(x) ((x)*(x))
  23. typedef long long ll;
  24. typedef long double ld;
  25. typedef pair<int, int> ii;
  26. const int INF = 1e9 + 7;
  27. const ld EPS = 1e-14;
  28. struct set_compare {
  29.     bool operator() (const pair<ll, int> a, const pair<ll, int> b) const{
  30.         return (a.first>b.first || a.first == b.first && a.second > b.second);
  31.     }
  32. };
  33.  
  34. const int NUM = 100007;
  35. ll dp[NUM][3] = { 0 };
  36. void init(){
  37.     for (int i = 0; i < NUM; i++){
  38.         for (int j = 0; j < 3; j++){
  39.             dp[i][j] = 0;
  40.         }
  41.     }
  42. }
  43. vector<ll> xs;
  44. vector<ll> xs1;
  45. vector<ll> hs;
  46. const ll INF_THIS = -1000008;
  47. int find_ind(ll x){
  48.     auto it = upper_bound(all(xs), x);
  49.     if (it == xs.end())
  50.         return -1;
  51.     else
  52.         return (int)(it-xs.begin());
  53. }
  54. int find_ind1(ll x){
  55.     auto it = upper_bound(all(xs1), x);
  56.     if (it == xs1.end())
  57.         return -1;
  58.     else
  59.         return (int)(it - xs1.begin());
  60. }
  61. //#define DEBUG
  62. int main(){
  63. #ifdef DEBUG
  64.     freopen("input.txt", "r", stdin);
  65.     freopen("output.txt", "w", stdout);
  66. #endif
  67.  
  68.     init();
  69.     int n;
  70.     cin >> n;  
  71.     xs.resize(n);
  72.     hs.resize(n);
  73.     xs1.resize(n);
  74.     for (int i = 0; i < xs.size(); i++){
  75.         cin >> xs[i] >> hs[i];
  76.         xs1[i] = xs[i] - hs[i];
  77.         if (i>0 && xs[i] - hs[i] <= xs[i - 1])
  78.             dp[i][1] = INF_THIS;
  79.     }
  80.     for (int i = 0; i < n - 1; i++){
  81.         if (xs[i] + hs[i] >= xs[i + 1])
  82.             dp[i][2] = INF_THIS;
  83.     }
  84.  
  85.     for (int i = n - 1; i >= 0; i--){
  86.         if (dp[i][0] == 0){
  87.             if (i + 1 < n) dp[i][0] = max(dp[i + 1][0], dp[i + 1][2]);
  88.             else
  89.                 dp[i][0] = 0;
  90.             int ind1 = find_ind1(xs[i]);
  91.             if (ind1 != -1 && dp[ind1][1]>=0) dp[i][0] = max(dp[i][0], dp[ind1][1]);
  92.             dp[i][0] = max(dp[i][0], 0ll);
  93.         }      
  94.  
  95.         if (dp[i][1] == 0){
  96.             if (i + 1 < n) dp[i][1] = max(dp[i + 1][0], dp[i + 1][2]) + 1;
  97.             else
  98.                 dp[i][1] = 1;
  99.             int ind1 = find_ind1(xs[i]);
  100.             if (ind1 != -1 && dp[ind1][1]>=0) dp[i][1] = max(dp[i][1], dp[ind1][1] + 1);
  101.             dp[i][1] = max(dp[i][1], 1ll);
  102.         }      
  103.  
  104.         if (dp[i][2] == 0){
  105.             int ind1 = find_ind(xs[i] + hs[i]);
  106.             if (ind1 != -1)
  107.                 dp[i][2] = max(dp[ind1][0], dp[ind1][2]) + 1;
  108.             else
  109.                 dp[i][2] = 1;
  110.             ind1 = find_ind1(xs[i] + hs[i]);
  111.             if (ind1 != -1 && dp[ind1][1]>=0) dp[i][2] = max(dp[i][2], dp[ind1][1] + 1);
  112.             dp[i][2] = max(dp[i][2], 1ll);
  113.         }      
  114.     }
  115.  
  116.     ll ans = 0;
  117.     ans = max(ans, dp[0][0]);
  118.     ans = max(ans, dp[0][1]);
  119.     ans = max(ans, dp[0][2]);
  120.     //if (ans == 1) while (true);
  121.     cout << ans;
  122.  
  123. #ifdef DEBUG
  124.     cerr << "Time elapsed: " << (ld)clock() / CLOCKS_PER_SEC << " sec." << endl;
  125. #endif
  126.     return 0;
  127. }
RAW Paste Data