Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pii pair<int, int>
- #define pb push_back
- #define mp make_pair
- #define f first
- #define s second
- using namespace std;
- typedef long long ll;
- typedef vector<int> big;
- const double EPS = 1e-9;
- const double PI = acos(-1);
- const int MAXN = (int) 1e3 + 7;
- const int INF = (int) 1e9 + 7;
- struct minQueue {
- pii sa[MAXN], sb[MAXN];
- int an, bn;
- minQueue() {
- an = bn = 0;
- }
- void push(int x) {
- sb[bn++] = mp(x, bn ? min(sb[bn - 1].s, x) : x);
- }
- void recalc() {
- while (bn) {
- int x = sb[bn - 1].f;
- sa[an++] = mp(x, an ? min(sa[an - 1].s, x) : x);
- bn--;
- }
- }
- int front() {
- assert(an + bn > 0);
- if (!an)
- recalc();
- return sa[an - 1].f;
- }
- void pop() {
- assert(an + bn > 0);
- if (!an)
- recalc();
- an--;
- }
- int getMin() {
- assert(an + bn > 0);
- if (!an) return sb[bn - 1].s;
- if (!bn) return sa[an - 1].s;
- return min(sa[an - 1].s, sb[bn - 1].s);
- }
- };
- int n, m, a, b, c, d;
- int f[MAXN][MAXN];
- int room[MAXN][MAXN];
- int pyramid[MAXN][MAXN];
- int nxtD[MAXN][MAXN];
- int nxtB[MAXN][MAXN];
- int sum[MAXN][MAXN];
- int main() {
- #ifdef LOCAL
- freopen("in", "r", stdin);
- #else
- //freopen(".in", "r", stdin);
- //freopen(".out", "w", stdout);
- #endif
- scanf("%d%d%d%d%d%d", &m, &n, &b, &a, &d, &c);
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- scanf("%d", &f[i][j]);
- sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + f[i][j];
- }
- }
- for (int i = 1; i <= n - c + 1; i++) {
- for (int j = 1; j <= m - d + 1; j++) {
- int x = i + c - 1;
- int y = j + d - 1;
- room[i][j] = sum[x][y] - sum[x][j - 1] - sum[i - 1][y] + sum[i - 1][j - 1];
- }
- }
- a -= 2;
- b -= 2;
- for (int i = 1; i <= n - c + 1; i++) {
- minQueue cur;
- for (int j = 1; j <= b - d + 1; j++) {
- cur.push(room[i][j]);
- }
- for (int j = 1; j <= (m - d + 1) - (b - d + 1) + 1; j++) {
- nxtB[i][j] = cur.getMin();
- if (j + (b - d + 1) <= m) {
- cur.pop();
- cur.push(room[i][j + b - d + 1]);
- }
- }
- }
- for (int j = 1; j <= (m - d + 1) - (b - d + 1) + 1; j++) {
- minQueue cur;
- for (int i = 1; i <= a - c + 1; i++)
- cur.push(nxtB[i][j]);
- for (int i = 1; i <= n - (a - c + 1) + 1; i++) {
- pyramid[i][j] = cur.getMin();
- if (i + (a - c + 1) <= n) {
- cur.pop();
- cur.push(nxtB[i + a - c + 1][j]);
- }
- }
- }
- a += 2;
- b += 2;
- long long ans = 0;
- int px = 0, py = 0;
- for (int i = 1; i <= n - a + 1; i++) {
- for (int j = 1; j <= m - b + 1; j++) {
- int ex = i + a - 1;
- int ey = j + b - 1;
- long long csum = sum[ex][ey] - sum[i - 1][ey] - sum[ex][j - 1] + sum[i - 1][j - 1];
- csum -= pyramid[i + 1][j + 1];
- if (csum > ans) {
- ans = csum;
- px = i;
- py = j;
- }
- }
- }
- printf("%d %d\n", py, px);
- //cout<<pyramid[px+1][py+1]<<endl;
- for (int i = px + 1; i + c - 1 < px + a - 1; i++) {
- for (int j = py + 1; j + d - 1 < py + b - 1; j++) {
- if (room[i][j] == pyramid[px + 1][py + 1]) {
- printf("%d %d\n", j, i);
- return 0;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment