Problem 8

#include <bits/stdc++.h>
using namespace std;
#define int int64_t

const int INF = 1e14;

struct rect {
    int i1, j1, i2, j2, su;
    rect() {}
    rect(int _i1, int _j1, int _i2, int _j2, int _su) : i1(_i1), j1(_j1), i2(_i2), j2(_j2), su(_su) {}
};

bool operator<(rect r1, rect r2) {
    return r1.su < r2.su;
}

int n, m;
vector<vector<int>> A;

void init() {
    A.assign(n, vector<int>(m));
}

rect solve() {
    rect ans = rect(-1, -1, -1, -1, -INF);
    vector<int> arr(n);
    for (int j1 = 0; j1 < m; ++j1) {
        arr.assign(n, 0);
        for (int j2 = j1; j2 < m; ++j2) {
            for (int i = 0; i < n; ++i)
                arr[i] += A[i][j2];
            pair<int, int> mi = make_pair(0, -1), ma = make_pair(0, -1);
            int ps = 0;
            for (int i = 0; i < n; ++i) {
                ps += arr[i];
                ma = max(ma, make_pair(ps - mi.first, i));
                ans = max(ans, rect(mi.second + 1, j1, ma.second, j2, ma.first));
                mi = min(mi, make_pair(ps, i));
            }
        }
    }
    return ans;
}

signed main() {
    cin >> n >> m, init();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> A[i][j];
    rect ans = solve();
    cout << ans.i1 << ',' << ans.j1 << ' ' << ans.i2 << ',' << ans.j2 << ": " << ans.su << endl;
}