Advertisement
Guest User

Untitled

a guest
Aug 30th, 2014
390
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <vector>  
  2. #include <list>  
  3. #include <map>  
  4. #include <set>  
  5. #include <deque>  
  6. #include <stack>  
  7. #include <algorithm>  
  8. #include <sstream>  
  9. #include <iostream>  
  10. #include <iomanip>  
  11. #include <cstdio>  
  12. #include <cmath>  
  13. #include <cstdlib>  
  14. #include <ctime>  
  15. #include <memory.h>  
  16.  
  17. #define ABS(a) ((a>0)?a:-(a))  
  18. #define MIN(a,b) ((a<b)?(a):(b))  
  19. #define MAX(a,b) ((a<b)?(b):(a))  
  20. #define FOR(i,a,n) for (int i=(a);i<(n);++i)  
  21. #define FI(i,n) for (int i=0; i<(n); ++i)  
  22. #define pnt pair <int, int>  
  23. #define mp make_pair  
  24. #define PI 3.14159265358979  
  25. #define MEMS(a,b) memset(a,b,sizeof(a))  
  26. #define LL long long  
  27. #define U unsigned
  28. using namespace std;
  29.  
  30. vector<pnt > a;
  31. int dp[1010][2];
  32. LL T;
  33.  
  34. int r(int p, int v)
  35. {
  36.     if (p == a.size())
  37.         return 0;
  38.     if (dp[p][v] != -1)
  39.         return dp[p][v];
  40.     int res = a.size();
  41.     if (v == 0)
  42.     {
  43.         FOR(i, p, a.size())
  44.         {
  45.             if (a[i].first - a[p].first <= T + T)
  46.             {
  47.                 res = min(res, 1 + r(i + 1, v));
  48.                 res = min(res, 1 + r(i + 1, v ^ 1));
  49.             }
  50.             else
  51.                 break;
  52.         }
  53.     }
  54.     else
  55.     {
  56.         LL rt = (LL)a[p].first - T - 1;
  57.         FOR(i, p, a.size())
  58.         {
  59.             LL le = MAX(a[i].first - T, rt + 1);
  60.             LL ri = a[i].first + T;
  61.             if (ri-le + 1 < a[i].second)
  62.                 break;
  63.             rt = le + a[i].second - 1;
  64.             res = min(res, r(i + 1, v ^ 1));
  65.             //res = min(res, r(i + 1, v));
  66.         }
  67.     }
  68.     return dp[p][v] = res;
  69. }
  70. class CatsOnTheLineDiv1 {
  71. public:
  72.     int getNumber(vector <int> position, vector <int> count, int t) {
  73.         int res = 0;
  74.         a.clear();
  75.         FOR(i, 0, position.size())
  76.             a.push_back(mp(position[i], count[i]));
  77.         int n = a.size();
  78.         sort(a.begin(), a.end());
  79.         MEMS(dp, -1);
  80.         T = t;
  81.         res = min(r(0, 0), r(0, 1));
  82.         return res;
  83.     }
  84.  
  85. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement