Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 1005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iii pair<int,ii>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "pyramid"
- #define int long long
- using namespace std;
- typedef long double ld;
- typedef vector<iii> viii;
- const int inf = 1e10;
- const int minf = -1e10;
- int n,m,a,b,c,d;
- int pf[N][N];
- int t[N][N];
- int get(int x, int y, int u, int v){
- return pf[u][v] - pf[u][y-1] - pf[x-1][v] + pf[x-1][y-1];
- }
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- freopen(Task".out","w",stdout);
- }
- cin >> n >> m >> b >> a >> d >> c;
- for(int i=1; i<=m; i++){
- for(int j=1; j<=n; j++){
- cin >> pf[i][j];
- pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + pf[i][j];
- }
- }
- memset(t, 0x3f3f3f3f3f, sizeof t);
- for(int i=1; i<=m-c+1; i++){
- for(int j=1; j<=n-d+1; j++){
- t[i][j] = get(i,j,i+c-1,j+d-1);
- }
- }
- }
- int fid[N][N];
- int f[N][N];
- int gid[N][N];
- int g[N][N];
- void proc()
- {
- int ans = 0;
- ii p1=ii(-1,-1), p2=ii(-1,-1);
- int lenx = a-c-1;
- int leny = b-d-1;
- for(int i=1; i<=m; i++){
- deque<int> q;
- int hi=1;
- for(int j=1; j+leny-1<=n; j++){
- while (hi<=n && hi<=j+leny-1){
- while (q.size() && t[i][q.back()]>=t[i][hi]) q.pop_back();
- q.pb(hi);
- ++hi;
- }
- while (q.size() && q.front()<j) q.pop_front();
- fid[i][j] = q.front();
- f[i][j] = t[i][q.front()];
- }
- }
- for(int j=1; j<=n; j++){
- deque<int> q;
- int hi=1;
- for(int lo=1; lo+lenx-1<=m; lo++){
- while (hi <= m && hi <= lo+lenx-1){
- while (q.size() && f[q.back()][j] >= f[hi][j]) q.pop_back();
- q.pb(hi);
- hi++;
- }
- while (q.size() && q.front()<lo) q.pop_front();
- gid[lo][j] = q.front();
- g[lo][j] = f[q.front()][j];
- }
- }
- int res=0;
- for(int i=1; i+a-1<=m; i++){
- for(int j=1; j+b-1<=n; j++){
- if (p1.fi==-1||p1.se==-1||get(i,j,i+a-1,j+b-1)-g[i+1][j+1]>res){
- res = get(i,j,i+a-1,j+b-1)-g[i+1][j+1];
- p1.fi = i;
- p1.se = j;
- }
- }
- }
- cout << p1.se << ' ' << p1.fi << '\n';
- p2.fi = gid[p1.fi+1][p1.se+1];
- p2.se = fid[p2.fi][p1.se+1];
- cout << p2.se << ' ' << p2.fi << '\n';
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement