Advertisement
Spark_code

Untitled

Jul 7th, 2013
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <iomanip>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <algorithm>
  9. #include <cmath>
  10. #include <sstream>
  11. #include <string>
  12. #include <memory.h>
  13.  
  14. using namespace std;
  15.  
  16. void prepare()
  17. {
  18. #ifdef _DEBUG
  19.     freopen("input.txt","r",stdin);
  20.     freopen("output.txt","w",stdout);
  21. #endif
  22. cin.sync_with_stdio(false);
  23. cout.sync_with_stdio(false);
  24. }
  25.  
  26. const int MAXINT = 200001;
  27. int t[MAXINT + 1], MAX[MAXINT + 1], n;
  28.  
  29. void rec(int i, int value)
  30. {
  31.     MAX[i] = value;
  32.     if (t[i] > 0 && i + t[i] <= MAXINT && MAX[i + t[i]] <= value)
  33.         rec(i + t[i], value + 1);
  34. }
  35.  
  36. int main()
  37. {
  38.     prepare();
  39.     cin >> n;
  40.  
  41.     for (int i = 0; i < n; i++)
  42.     {
  43.         int t1, td;
  44.         cin >> t1 >> td;
  45.         t[t1] = max(td, t[t1]);
  46.     }
  47.  
  48.     for (int i = 0; i < MAXINT + 1; i++)
  49.     {
  50.         MAX[i] = -1;
  51.     }
  52.  
  53.     //memset(MAX, 255, MAXINT + 1);
  54.     MAX[0] = 0;
  55.  
  56.     for (int i = 1; i < MAXINT + 1 ; i++)
  57.     {
  58.         MAX[i] = max(MAX[i], MAX[i - 1]);
  59.  
  60.         if (t[i] > 0 && i + t[i] <= MAXINT && MAX[i + t[i]] <= MAX[i])
  61.             rec(i + t[i], MAX[i] + 1);
  62.     }
  63.  
  64.     cout << MAX[MAXINT];
  65.  
  66.     return 0;
  67.  
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement