IOI '06 P2 - Pyramid

#include <iostream>
#include <vector>
#include <set>
#include <tuple>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m, n, a, b, c, d;
    cin >> m >> n >> a >> b >> c >> d;
    vector<vector<int>> g(1+n, vector<int>(1+m));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int x; cin >> x;
            g[i][j] += x;
            if (j < m) g[i][j+1] += g[i][j];
            g[i][j] += g[i-1][j];
        }
    }
    auto rect = [&g](int r1, int c1, int r2, int c2) {
        --r1, --c1;
        return g[r2][c2] - g[r1][c2] - g[r2][c1] + g[r1][c1];
    };
    vector<vector<int>> A(1+n + 1-b, vector<int>(1+m + 1-a));
    vector<vector<int>> B(1+n + 1-d, vector<int>(1+m + 1-c));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i <= n+1-b && j <= m+1-a) A[i][j] = rect(i, j, i+b-1, j+a-1);
            if (i <= n+1-d && j <= m+1-c) B[i][j] = rect(i, j, i+d-1, j+c-1);
        }
    }

    int maxSum = 0;
    int iBase = -1, jBase = -1, iChamber = -1, jChamber = -1;

    vector<set<pair<int, int>>> columnActive(1+m + 1-c);
    for (int i = 2; i < 1+b-d; ++i) {
        for (int j = 1; j <= m+1-c; ++j) columnActive[j].emplace(B[i][j], i);
    }

    for (int i = 1; i <= n+1-b; ++i) {
        set<tuple<int, int, int>> s;
        for (int j = 2; j < 1+a-c; ++j) {
            auto [sum, row] = *columnActive[j].begin();
            s.emplace(sum, row, j);
        }
        for (int j = 1; j <= m+1-a; ++j) {
            int baseSum = A[i][j];
            tuple<int, int, int> t = *s.begin();
            int chamberSum = get<0>(t);
            int chamberI = get<1>(t), chamberJ = get<2>(t);
            if (baseSum-chamberSum > maxSum) {
                maxSum = baseSum-chamberSum;
                iBase = i, jBase = j;
                iChamber = chamberI, jChamber = chamberJ;
            }
            if (j+1 <= m+1-a) { // update s
                auto [sum, row] = *columnActive[j+1].begin();
                s.erase({sum, row, j+1});
                tie(sum, row) = *columnActive[j+a-c].begin();
                s.emplace(sum, row, j+a-c);
            }
        }

        if (i+1 <= n+1-b) { // update columnActive
            for (int j = 1; j <= m+1-c; ++j) {
                columnActive[j].erase({B[i+1][j], i+1});
                columnActive[j].insert({B[i+b-d][j], i+b-d});
            }
        }
    }

    cout << jBase << ' ' << iBase << '\n' << jChamber << ' ' << iChamber << '\n';
    return 0;
}