Advertisement
MinhNGUYEN2k4

Untitled

Sep 12th, 2021
824
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define TASK "PYRAMID"
  3. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  4. #define READFILE freopen(TASK".INP","r",stdin)
  5. #define WRITEFILE freopen(TASK".OUT","w",stdout)
  6. #define For(i,a,b) for(int i=a;i<=b;i++)
  7. #define Rep(i,a,b) for(int i=a;i>=b;i--)
  8. #define pb push_back
  9. #define ENDL '\n'
  10. #define debug(x) cout<<#x<<" = "<<x<<ENDL
  11. #define fi first
  12. #define se second
  13. #define ever (;true;)
  14. #define all(x) x.begin(),x.end()
  15. #define sz(a) ((int)(a).size())
  16. #define ms(a,x) memset(a,x,sizeof(a))
  17. #define int long long
  18.  
  19. using namespace std;
  20. typedef vector <int> vi;
  21. typedef pair <int,int> ii;
  22. typedef vector <ii> vpi;
  23. typedef pair <int,ii> iii;
  24. const int N = 1010;
  25. const int oo=0x3f;
  26. const int mod=1e9+7;
  27. const int dx[]={0,1,0,-1,0};
  28. int n,m,a,b,c,d,pre[N][N];
  29. ii pos[N][N];
  30. iii st[N*4][N];
  31. int calc(int i, int j){
  32.     return pre[i+c-1][j+d-1]-pre[i-1][j+d-1]-pre[i+c-1][j-1]+pre[i-1][j-1];
  33. }
  34. void build(int id, int l, int r, int x){
  35.     if (l==r){
  36.         st[id][x]=iii(pos[l][x].fi,ii(l,pos[l][x].se));
  37.         return;
  38.     }
  39.     int m=(l+r)>>1;
  40.     build(id<<1,l,m,x);
  41.     build(id<<1|1,m+1,r,x);
  42.     st[id][x]=min(st[id<<1][x],st[id<<1|1][x]);
  43. }
  44. iii get(int id, int l, int r, int x, int u, int v){
  45.     if (u>r || v<l) return iii(LLONG_MAX,ii(LLONG_MAX,LLONG_MAX));
  46.     if (u<=l && r<=v) return st[id][x];
  47.     int m=(l+r)>>1;
  48.     return min(get(id<<1,l,m,x,u,v),get(id<<1|1,m+1,r,x,u,v));
  49. }
  50. void proc(){
  51.     ii nen,tuong;
  52.     int ans=-1;
  53.     For(i,1,n-a+1)
  54.         For(j,1,m-b+1){
  55.             int sq=pre[i+a-1][j+b-1]-pre[i-1][j+b-1]-pre[i+a-1][j-1]+pre[i-1][j-1];
  56.             iii mi;
  57.             mi=get(1,2,n-c,j+1,i+1,i+a-c-1);
  58.             if (ans<sq-mi.fi){
  59.                 ans=sq-mi.fi;
  60.                 nen.fi=i;
  61.                 nen.se=j;
  62.                 tuong.fi=mi.se.fi;
  63.                 tuong.se=mi.se.se;
  64.             }
  65.         }
  66.     cout << nen.se << ' ' << nen.fi << ENDL;
  67.     cout << tuong.se << ' ' << tuong.fi;
  68. }
  69. void init(){
  70.   FAST;
  71.   READFILE;
  72.   WRITEFILE;
  73.   cin >> m >> n >> b >> a >> d >> c;
  74.   For(i,1,n)
  75.     For(j,1,m){
  76.         int x;
  77.         cin >> x;
  78.         pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+x;
  79.     }
  80.   ms(pos,oo);
  81.   For(i,2,n-c){
  82.     deque<int> dq;
  83.     For(j,2,m-d){
  84.         int sq=calc(i,j);
  85.         while (dq.size() && calc(i,dq.back())>=sq) dq.pop_back();
  86.         dq.push_back(j);
  87.         while(dq.size() && j-dq.front()+1>b-d-1) dq.pop_front();
  88.         if (j>=b-d) pos[i][j-(b-d-2)]={calc(i,dq.front()),dq.front()};
  89.     }
  90.   }
  91.   For(j,2,m-b+2) build(1,2,n-c,j);
  92. }
  93. signed main()
  94. {
  95.   init();
  96.   proc();
  97.   return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement