FHVirus

Untitled

Jan 2nd, 2021
312
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. //Knapsack DP is harder than FFT.
  2. #include<unistd.h>
  3. inline char RC(){static char buf[65536],*p=buf,*q=buf;return p==q&&(q=(p=buf)+read(0,buf,65536))==buf?-1:*p++;}
  4. 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;}
  5. 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);}
  6.  
  7. #include<algorithm>
  8. #include<vector>
  9. using namespace std;
  10. typedef pair<int,int> pii;
  11. #define FOR(i,n) for(int i=0;i<(n);++i)
  12. #define ff first
  13. #define ss second
  14.  
  15. const int N = 3000;
  16. int n, l, w;
  17. pii p[N];
  18. vector<int> v;
  19.  
  20. int main(){
  21.     n = R(), l = R(), w = R();
  22.     FOR(i,n) p[i].ff = R(), p[i].ss = R(), v.push_back(p[i].ss);
  23.     sort(p, p + n);
  24.     sort(v.begin(), v.end());
  25.     v.resize(unique(v.begin(), v.end()) - v.begin());
  26.  
  27.     int ans = 0;
  28.     for(int y: v){
  29.         int lptr = 0, rptr = 1, cnt = 0;
  30.         if(p[0].ss >= y and p[0].ss - y <= l) ++cnt;
  31.         for(; lptr < n; ++lptr){
  32.             if(rptr == n) break;
  33.             while(rptr < n and p[rptr].ff - p[lptr].ff <= w){
  34.                 if(p[rptr].ss >= y and p[rptr].ss - y <= l) ++cnt;
  35.                 ++rptr;
  36.             }
  37.             ans = max(ans, cnt);
  38.             if(p[lptr].ss >= y and p[lptr].ss - y <= l) --cnt;
  39.         }
  40.     }
  41.     W(ans);
  42.     return 0;
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment