Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define TASK "PYRAMID"
- #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
- #define READFILE freopen(TASK".INP","r",stdin)
- #define WRITEFILE freopen(TASK".OUT","w",stdout)
- #define For(i,a,b) for(int i=a;i<=b;i++)
- #define Rep(i,a,b) for(int i=a;i>=b;i--)
- #define pb push_back
- #define ENDL '\n'
- #define debug(x) cout<<#x<<" = "<<x<<ENDL
- #define fi first
- #define se second
- #define ever (;true;)
- #define all(x) x.begin(),x.end()
- #define sz(a) ((int)(a).size())
- #define ms(a,x) memset(a,x,sizeof(a))
- #define int long long
- using namespace std;
- typedef vector <int> vi;
- typedef pair <int,int> ii;
- typedef vector <ii> vpi;
- typedef pair <int,ii> iii;
- const int N = 1010;
- const int oo=0x3f;
- const int mod=1e9+7;
- const int dx[]={0,1,0,-1,0};
- int n,m,a,b,c,d,pre[N][N];
- ii pos[N][N];
- iii st[N*4][N];
- int calc(int i, int j){
- 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];
- }
- void build(int id, int l, int r, int x){
- if (l==r){
- st[id][x]=iii(pos[l][x].fi,ii(l,pos[l][x].se));
- return;
- }
- int m=(l+r)>>1;
- build(id<<1,l,m,x);
- build(id<<1|1,m+1,r,x);
- st[id][x]=min(st[id<<1][x],st[id<<1|1][x]);
- }
- iii get(int id, int l, int r, int x, int u, int v){
- if (u>r || v<l) return iii(LLONG_MAX,ii(LLONG_MAX,LLONG_MAX));
- if (u<=l && r<=v) return st[id][x];
- int m=(l+r)>>1;
- return min(get(id<<1,l,m,x,u,v),get(id<<1|1,m+1,r,x,u,v));
- }
- void proc(){
- ii nen,tuong;
- int ans=-1;
- For(i,1,n-a+1)
- For(j,1,m-b+1){
- 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];
- iii mi;
- mi=get(1,2,n-c,j+1,i+1,i+a-c-1);
- if (ans<sq-mi.fi){
- ans=sq-mi.fi;
- nen.fi=i;
- nen.se=j;
- tuong.fi=mi.se.fi;
- tuong.se=mi.se.se;
- }
- }
- cout << nen.se << ' ' << nen.fi << ENDL;
- cout << tuong.se << ' ' << tuong.fi;
- }
- void init(){
- FAST;
- READFILE;
- WRITEFILE;
- cin >> m >> n >> b >> a >> d >> c;
- For(i,1,n)
- For(j,1,m){
- int x;
- cin >> x;
- pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+x;
- }
- ms(pos,oo);
- For(i,2,n-c){
- deque<int> dq;
- For(j,2,m-d){
- int sq=calc(i,j);
- while (dq.size() && calc(i,dq.back())>=sq) dq.pop_back();
- dq.push_back(j);
- while(dq.size() && j-dq.front()+1>b-d-1) dq.pop_front();
- if (j>=b-d) pos[i][j-(b-d-2)]={calc(i,dq.front()),dq.front()};
- }
- }
- For(j,2,m-b+2) build(1,2,n-c,j);
- }
- signed main()
- {
- init();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement