F 阎小罗的Minimax （第十届山东理工大学ACM网络编程擂台赛 正式赛 ）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef long long ll;
ll a[505][505];
ll min(ll x, ll y)
{
    if(x > y)
        return y;
    else
        return x;
}
ll max(ll x, ll y)
{
    if(x < y)
        return y;
    else
        return x;
}
int main()
{
    ll t, n, m, i, j;
    scanf("%lld", &t);
    assert(1 <= t && t <= 10);
    while(t--)
    {
        memset(a, 0, sizeof(a));
        scanf("%lld %lld", &n, &m);
        assert(n >= 3 && n <= 300 && m >= 3 && m <= 300);
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= m; j++)
            {
                scanf("%lld", &a[i][j]);
                assert(a[i][j] >= 0 && a[i][j] <= 1000000000);
                a[i][j] += a[i][j - 1];
            }
            for(j = 1; j <= m; j++)
            {
                a[i][j] += a[i - 1][j];
            }
        }
        ll ans = 0x3fffffffffff;
        for(i = 2; i < n; i++)
        {
            for(j = 2; j < m; j++)
            {
                ll aa, bb, cc, dd;
                aa = a[i - 1][j - 1];
                bb = a[i - 1][m] - a[i - 1][j];
                cc = a[n][j - 1] - a[i][j - 1];
                dd = a[n][m] - a[n][j] - (a[i][m] - a[i][j]);
                ll maxx = max(max(aa, bb), max(cc, dd));
                ll minn = min(min(aa, bb), min(cc, dd));
                ans = min(maxx - minn, ans);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}