Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <iomanip>
#include <stack>
#include <queue>
#include <ctime>

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define LL long long
#define LD long double
#define VI vector<int>
#define II pair<int, int>
#define MP make_pair
#define X first
#define Y second
#define PB push_back
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define endl '\n'

const int N = 1010;
const LL oo = 100000000000000000ll;

using namespace std;

LL s[N][N];
int a[N][N];
int n, m, k;

LL sum(int x, int y, int u, int v) {
    return s[u][v] - s[x - 1][v] - s[u][y - 1] + s[x - 1][y - 1];
}

void mini(LL &a, LL b) {a = a > b ? b : a;}
LL myabs(LL a) {return a > 0 ? a : (-a);}

void naive() {
    int x, y, u, v;
    FOR(step, 0, k){
        cin >> x >> y >> u >> v;
        LL ans = oo;
        FOR(i, x, u)
            mini(ans, myabs(sum(x, y, i, v) - sum(i + 1, y, u, v)));
        FOR(j, y, v)
            mini(ans, myabs(sum(x, y, u, j) - sum(x, j + 1, u, v)));
        cout << ans << endl;
    }
};

LL getMinX(int &x, int &y, int &u, int &v) {
    int l = x, r = u - 1, k = x;
    while (l <= r) {
        int mid = l + r >> 1;
        if (sum(x, y, mid, v) <= sum(mid + 1, y, u, v)) {
            k = mid; l = mid + 1;
        }
        else
            r = mid - 1;
    }
    LL ret = myabs(sum(x, y, k, v) - sum(k + 1, y, u, v));
    if (k + 1 < u) mini(ret, myabs(sum(x, y, k + 1, v) - sum(k + 2, y, u, v)));
    return ret;
}

LL getMinY(int &x, int &y, int &u, int &v) {
    int l = y, r = v - 1, k = y;
    while (l <= r) {
        int mid = l + r >> 1;
        if (sum(x, y, u, mid) <= sum(x, mid + 1, u, v)) {
            k = mid; l = mid + 1;
        }
        else
            r = mid - 1;
    }
    LL ret = myabs(sum(x, y, u, k) - sum(x, k + 1, u, v));
    if (k + 1 < v) mini(ret, myabs(sum(x, y, u, k + 1) - sum(x, k + 2, u, v)));
    return ret;
}

void optimal() {
    int x, y, u, v;
    while (k--) {
        cin >> x >> y >> u >> v;
        LL ans = oo;
        if (x < u)
            mini(ans, getMinX(x, y, u, v));
        if (y < v)
            mini(ans, getMinY(x, y, u, v));
        cout << ans << '\n';
        //printf("%lld\n", ans);
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> m >> n >> k;
    //scanf("%d%d%d", &m, &n, &k);
    REP(i, 1, m) REP(j, 1, n)
        cin >> a[i][j];
        //scanf("%d", &a[i][j]);
    REP(i, 1, m) REP(j, 1, n)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    if (m <= 100 && n <= 100)
        naive();
    else
        optimal();
    return 0;
}