IOI 2006 B Pyramid

/*
    Solution by Zalkar aka KGZ
*/

#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define sz(s) (int) s.size ()
#define all(s) s.begin (), s.end ()

#define filename "file"

using namespace std;

const int N = 1500;
const int INF = 1e9 + 7;

int a[N][N], n ,m, n1, m1, n2, m2, sum[N][N], ans;

int getsum (int lx, int ly, int rx, int ry) {
    return sum[rx][ry] - sum[lx - 1][ry] - sum[rx][ly - 1] + sum[lx - 1][ly - 1];
}

int main ()
{
    int x1, y1, x2, y2;

    scanf ("%d %d %d %d %d %d", &m, &n, &m1, &n1, &m2, &n2);

    for (int c = 1; c <= n; c++) {
        for (int i = 1; i <= m; i++) {
            scanf ("%d", &a[c][i]);
            sum[c][i] = a[c][i];
            sum[c][i] += sum[c - 1][i];
            sum[c][i] += sum[c][i - 1];
            sum[c][i] -= sum[c - 1][i - 1];
        }
    }

    for (int c = 1; c <= n - n1 + 1; c++) {
        for (int i = 1; i <= m - m1 + 1; i++) {

            int sumofpyramid = getsum (c, i, c + n1 - 1, i + m1 - 1);
            int mn = INF;
            int curx, cury;

            for (int j = c + 1; j <= (c + n1 - 2) - n2 + 1; j++) {
                for (int k = i + 1; k <= (i + m1 - 2) - m2 + 1; k++) {

                    if (getsum (j, k, j + n2 - 1, k + m2 - 1) < mn) {
                        mn = getsum (j, k, j + n2 - 1, k + m2 - 1);
                        curx = j; cury = k;
                    }
                }
            }

            sumofpyramid -= mn;

            if (sumofpyramid > ans) {
                ans = sumofpyramid;
                x1 = c; y1 = i;
                x2 = curx; y2 = cury;
            }
        }
    }

    printf("%d %d\n", y1, x1);
    printf("%d %d\n", y2, x2);


    return 0;
}