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 = 1111;
- int a[N][N], sum[N][N];
- int n, m;
- int A, B, C, D;
- int aa[N][N];
- inline void gen()
- {
- n = m = 100;
- forn1(i, n)
- {
- forn1(j, m)
- {
- a[i][j] = rand() % 100 + 1;
- }
- }
- A = rand() % n + 1;
- while(A <= 10)
- A = rand() % n + 1;
- B = rand() % m + 1;
- while(B <= 10)
- B = rand() % m + 1;
- C = rand() % (A - 2) + 1;
- D = rand() % (B - 2) + 1;
- return;
- }
- inline bool read()
- {
- //gen();
- //return true;
- 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 = 12;
- int 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)
- {
- assert(rg >= lf);
- 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)
- {
- if(!(i2 >= i1 && j2 >= j1))
- {
- cerr << i1 << ' ' << i2 << ' ' << j1 << ' ' << j2 << endl;
- assert(false);
- }
- return sum[i2][j2] - sum[i2][j1 - 1] - sum[i1 - 1][j2] + sum[i1 - 1][j1 - 1];
- }
- inline int naive()
- {
- int res = -1;
- forn1(i, n)
- {
- forn1(j, m)
- {
- int i2 = i + A - 1, j2 = j + B - 1;
- if(i2 > n || j2 > m)
- continue;
- int cur = getSum(i, j, i2, j2);
- //cerr << "i j sum == " << i << ' ' << j << ' ' << cur << endl;
- //cerr << i2 << ' ' << j2 << endl;
- int mn = INF;
- for(int ii = i + 1; ii <= i2 - 1; ii++)
- {
- for(int jj = j + 1; jj <= j2 - 1; jj++)
- {
- int ii2 = ii + C - 1, jj2 = jj + D - 1;
- if(ii2 >= i2 || jj2 >= j2)
- continue;
- mn = min(mn, getSum(ii, jj, ii2, jj2));
- }
- }
- res = max(res, cur - mn);
- }
- }
- assert(res >= 0);
- return res;
- }
- 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);
- }
- //cerr << "B == " << endl;
- //forn1(j, m)
- // cerr << b[j] << ' ';
- //cerr << endl;
- multiset<int> S;
- //cerr << "i == " << ii << endl;
- int last = -1;
- for(int j = 2; j < B; j++)
- {
- int jj = j + D - 1;
- //cerr << "jj == " << j << ' ' << jj << endl;
- if(jj >= B)
- break;
- S.insert(b[j]);
- last = j;
- }
- assert(last >= 1);
- int init = getSum(ii, 1, ii + A - 1, B);
- //cerr << "initsum == " << init << endl;
- //cerr << "initMin == " << *S.begin() << endl;
- init -= *S.begin();
- if(init >= ans)
- {
- //cerr << "INIT == "<< init << endl;
- ans = init;
- res = mp(ii, 1);
- }
- //cerr << "szs == " << sz(S) << endl;
- int ins = 2;
- for(int j = B + 1; j <= m; j++)
- {
- //cerr << "SZS == " << sz(S) << endl;
- //for(multiset<int>::iterator it = S.begin(); it != S.end(); it++)
- // cerr << *it << ' ';
- //cerr << endl;
- //cerr << "j == " << j << endl;
- //cerr << "insert == " << b[j - 1] << endl;
- //cerr << "remove == " << b[j - D - 2] << endl;
- S.insert(b[++last]);
- //S.erase(S.end());
- //cerr << "rem == " << j - D - 2 << endl;
- S.erase(S.find(b[ins++]));
- //cerr << "removed" << endl;
- int cur = getSum(ii, j - B + 1, ii + A - 1, j) - *S.begin();
- if(cur >= ans)
- {
- ans = cur;
- res = mp(ii, j - B + 1);
- }
- }
- }
- //cerr << "RES == " << res.x << ' ' << res.y << endl;
- assert(ans >= 0);
- return ans;
- }
- inline void solve()
- {
- //buildMin();
- 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);
- #ifdef _DEBUG
- int nans = naive();
- if(ans != nans)
- {
- cerr << ans << ' ' << nans << endl;
- assert(false);
- }
- #endif
- 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);
- }
- }
- }
- cerr << ans << endl;
- 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)));
- forn(i, 1)
- {
- assert(read());
- solve();
- }
- #ifdef _DEBUG
- cerr << "TIME == " << clock() << " ms" << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment