Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <stack>
- #include <algorithm>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <ctime>
- #include <memory.h>
- #define ABS(a) ((a>0)?a:-(a))
- #define MIN(a,b) ((a<b)?(a):(b))
- #define MAX(a,b) ((a<b)?(b):(a))
- #define FOR(i,a,n) for (int i=(a);i<(n);++i)
- #define FI(i,n) for (int i=0; i<(n); ++i)
- #define pnt pair <int, int>
- #define mp make_pair
- #define PI 3.14159265358979
- #define MEMS(a,b) memset(a,b,sizeof(a))
- #define LL long long
- #define U unsigned
- using namespace std;
- vector<pnt > a;
- int dp[1010][2];
- LL T;
- int r(int p, int v)
- {
- if (p == a.size())
- return 0;
- if (dp[p][v] != -1)
- return dp[p][v];
- int res = a.size();
- if (v == 0)
- {
- FOR(i, p, a.size())
- {
- if (a[i].first - a[p].first <= T + T)
- {
- res = min(res, 1 + r(i + 1, v));
- res = min(res, 1 + r(i + 1, v ^ 1));
- }
- else
- break;
- }
- }
- else
- {
- LL rt = (LL)a[p].first - T - 1;
- FOR(i, p, a.size())
- {
- LL le = MAX(a[i].first - T, rt + 1);
- LL ri = a[i].first + T;
- if (ri-le + 1 < a[i].second)
- break;
- rt = le + a[i].second - 1;
- res = min(res, r(i + 1, v ^ 1));
- //res = min(res, r(i + 1, v));
- }
- }
- return dp[p][v] = res;
- }
- class CatsOnTheLineDiv1 {
- public:
- int getNumber(vector <int> position, vector <int> count, int t) {
- int res = 0;
- a.clear();
- FOR(i, 0, position.size())
- a.push_back(mp(position[i], count[i]));
- int n = a.size();
- sort(a.begin(), a.end());
- MEMS(dp, -1);
- T = t;
- res = min(r(0, 0), r(0, 1));
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement