Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Knapsack DP is harder than FFT.
- #include<unistd.h>
- inline char RC(){static char buf[65536],*p=buf,*q=buf;return p==q&&(q=(p=buf)+read(0,buf,65536))==buf?-1:*p++;}
- inline int R(){static char c;int a;while((c=RC())<'0');a=c^'0';while((c=RC())>='0')a*=10,a+=c^'0';return a;}
- inline void W(int n){char OB[12],OP=0,buf[12],p;if(n==0)OB[OP++]='0';p=0;while(n)buf[p++]='0'+(n%10),n/=10;for(--p;p>=0;--p)OB[OP++]=buf[p];write(1,OB,OP);}
- #include<algorithm>
- #include<vector>
- using namespace std;
- typedef pair<int,int> pii;
- #define FOR(i,n) for(int i=0;i<(n);++i)
- #define ff first
- #define ss second
- const int N = 3000;
- int n, l, w;
- pii p[N];
- vector<int> v;
- int main(){
- n = R(), l = R(), w = R();
- FOR(i,n) p[i].ff = R(), p[i].ss = R(), v.push_back(p[i].ss);
- sort(p, p + n);
- sort(v.begin(), v.end());
- v.resize(unique(v.begin(), v.end()) - v.begin());
- int ans = 0;
- for(int y: v){
- int lptr = 0, rptr = 1, cnt = 0;
- if(p[0].ss >= y and p[0].ss - y <= l) ++cnt;
- for(; lptr < n; ++lptr){
- if(rptr == n) break;
- while(rptr < n and p[rptr].ff - p[lptr].ff <= w){
- if(p[rptr].ss >= y and p[rptr].ss - y <= l) ++cnt;
- ++rptr;
- }
- ans = max(ans, cnt);
- if(p[lptr].ss >= y and p[lptr].ss - y <= l) --cnt;
- }
- }
- W(ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment