Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <fstream>
- #include <iomanip>
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <queue>
- #include <stack>
- #include <set>
- #include <map>
- #include <list>
- #include <vector>
- #include <string>
- #include <cstring>
- #include <cmath>
- #include <ctime>
- #include <cassert>
- #include <bitset>
- using namespace std;
- #define forn(i, n) for(int i = 0; i < (int)(n); i++)
- #define forn1(i, n) for(int i = 1; i <= (int)(n); i++)
- #define all(a) (a).begin(), (a).end()
- #define sz(a) (int)((a).size())
- #define mp make_pair
- #define pb push_back
- #define X first
- #define Y second
- #define x first
- #define y second
- #define y1 __y1
- #define sqr(x) ((x) * (x))
- typedef long long li;
- typedef long double ld;
- typedef pair<li, li> pt;
- const int INF = (int)(1e9);
- const li INF64 = (li)(INF) * (li)(INF);
- const ld eps = 3e-8;
- const ld pi = ld(3.1415926535897932384626433832795);
- bool in(int i, int j, int n, int m)
- {
- return i >= 1 && i <= n && j >= 1 && j <= m;
- }
- inline int myrand()
- {
- return (rand() ^ (rand() << 15));
- }
- const int dx[] = {-1, 0, 1, 0};
- const int dy[] = {0, 1, 0, -1};
- const int N = 1001;
- short a[N][N];
- int sum[N][N];
- int n, m;
- int A, B, C, D;
- short aa[N][N];
- inline bool read()
- {
- if(scanf("%d %d", &m, &n) != 2)
- return false;
- assert(scanf("%d %d %d %d", &A, &B, &C, &D) == 4);
- swap(A, B);
- swap(C, D);
- forn1(i, n)
- {
- forn1(j, m)
- {
- assert(scanf("%d", &a[i][j]) == 1);
- }
- }
- return true;
- }
- const int LOG = 10;
- short Min[N][N][LOG];
- int pow2[N], lg2[N];
- inline void buildMin()
- {
- pow2[0] = 1;
- for(int i = 1; i < N; i++)
- {
- pow2[i] = pow2[i - 1] * 2;
- }
- for(int i = 1; i < N; i++)
- {
- int res = 0, cur = 1;
- while(cur <= i)
- {
- cur *= 2;
- res++;
- }
- lg2[i] = res - 1;
- }
- forn1(j, m)
- {
- forn(pow, LOG)
- {
- forn1(i, n)
- {
- if(pow == 0)
- {
- Min[j][i][pow] = aa[i][j];
- }
- else
- {
- if(i + pow2[pow] - 1 <= n)
- {
- Min[j][i][pow] = min(Min[j][i][pow - 1], Min[j][i + pow2[pow - 1]][pow - 1]);
- }
- }
- }
- }
- }
- return;
- }
- inline int getMin(int idx, int lf, int rg)
- {
- int len = rg - lf + 1;
- return min(Min[idx][lf][lg2[len]], Min[idx][rg - pow2[lg2[len]] + 1][lg2[len]]);
- }
- inline int getSum(int i1, int j1, int i2, int j2)
- {
- return sum[i2][j2] - sum[i2][j1 - 1] - sum[i1 - 1][j2] + sum[i1 - 1][j1 - 1];
- }
- int b[N];
- inline int solve(pt &res)
- {
- int ans = -1;
- forn1(ii, n)
- {
- if(ii + A - 1 > n)
- continue;
- forn1(j, m)
- {
- b[j] = getMin(j, ii + 1, ii + A - 1 - C);
- }
- multiset<int> S;
- int last = -1;
- for(int j = 2; j < B; j++)
- {
- int jj = j + D - 1;
- if(jj >= B)
- break;
- S.insert(b[j]);
- last = j;
- }
- int init = getSum(ii, 1, ii + A - 1, B);
- init -= *S.begin();
- if(init >= ans)
- {
- ans = init;
- res = mp(ii, 1);
- }
- int ins = 2;
- for(int j = B + 1; j <= m; j++)
- {
- S.insert(b[++last]);
- S.erase(S.find(b[ins++]));
- int cur = getSum(ii, j - B + 1, ii + A - 1, j) - *S.begin();
- if(cur >= ans)
- {
- ans = cur;
- res = mp(ii, j - B + 1);
- }
- }
- }
- return ans;
- }
- inline void solve()
- {
- forn1(i, n)
- {
- int s = 0;
- forn1(j, m)
- {
- s += a[i][j];
- sum[i][j] = sum[i - 1][j] + s;
- }
- }
- forn1(i, n)
- {
- forn1(j, m)
- {
- if(i + C - 1 > n || j + D - 1 > m)
- continue;
- aa[i][j] = getSum(i, j, i + C - 1, j + D - 1);
- }
- }
- buildMin();
- pt res1 = mp(0, 0);
- int ans = solve(res1);
- pt res2 = mp(0, 0);
- int mn = INF;
- for(int i = res1.x + 1; i <= res1.x + A - 1; i++)
- {
- for(int j = res1.y + 1; j <= res1.y + B - 1; j++)
- {
- if(i + C - 1 >= res1.x + A - 1 || j + D - 1 >= res1.y + B - 1)
- continue;
- int cur = getSum(i, j, i + C - 1, j + D - 1);
- if(cur < mn)
- {
- mn = cur;
- res2 = mp(i, j);
- }
- }
- }
- swap(res1.x, res1.y);
- swap(res2.x, res2.y);
- cout << res1.x << ' ' << res1.y << endl;
- cout << res2.x << ' ' << res2.y << endl;
- return;
- }
- int main() {
- #ifdef _DEBUG
- assert(freopen("input.txt", "rt", stdin));
- assert(freopen("output.txt", "wt", stdout));
- #endif
- cout << setprecision(10) << fixed;
- cerr << setprecision(10) << fixed;
- srand(int(time(NULL)));
- assert(read());
- solve();
- #ifdef _DEBUG
- cerr << "TIME == " << clock() << " ms" << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment