## Editorial for VOI 15 Bài 4 - Cắt hình

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

#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;
}