UVa 10827

#include<bits/stdc++.h>

using namespace std;

#define Max 160

int N;
int M[Max][Max];

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int tcase;
    scanf("%d", &tcase);
    while(tcase--) {
        scanf("%d", &N);
        for(int i = 0, n = N * 2 - 1; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i < N and j < N) {
                    scanf("%d", &M[i][j]);
                    M[i + N][j] = M[i][j + N] = M[i + N][j + N] = M[i][j];
                }
                if(i > 0) M[i][j] += M[i - 1][j];
                if(j > 0) M[i][j] += M[i][j - 1];
                if(i > 0 and j > 0) M[i][j] -= M[i - 1][j - 1];
            }
        }
        int ans = INT_MIN;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                for(int k = i; k < i + N; k++) {
                    for(int l = j; l < j + N; l++) {
                        int sum = M[k][l];
                        if(i > 0) sum -= M[i - 1][l];
                        if(j > 0) sum -= M[k][j - 1];
                        if(i > 0 and j > 0) sum += M[i - 1][j - 1];
                        ans = max(ans, sum);
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
}
/* WA (still don't know why)
#include <bits/stdc++.h>

using namespace std;

#define Max 160

int N, M[Max][Max], temp[Max];

int kadane() {
    int sum = 0, maxSum = INT_MIN;
    bool allNegative = true;

    for(int i = 0; i < N; i++) {
        sum = 0;
        for(int j = i; j < N + i; j++) {
            sum += temp[j];
            if(sum < 0) {
                sum = 0;
            } else if(sum > maxSum) {
                maxSum = sum;
                allNegative = false;
            }
        }
    }

    if(!allNegative)
        return maxSum;

    maxSum = temp[0];

    for(int i = 1, n = 2 * N - 1; i < n; i++)
        maxSum = max(maxSum, temp[i]);

    return maxSum;
}

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int tcase;
    scanf("%d", &tcase);
    while (tcase--) {
        scanf("%d", &N);
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                scanf("%d", &M[i][j]);
                M[i][j + N] = M[i][j];
            }
        }
        for(int i = 0; i < N; i++) {
            for(int j = 0, n = 2 * N - 1; j < n; j++) {
                M[i + N][j] = M[i][j];
            }
        }

        int maxSum = INT_MIN;
        int row = 2 * N - 1, col = 2 * N - 1;

        for(int left = 0; left < col; ++left) {
            memset(temp, 0, sizeof temp);
            for(int right = left; right < col; ++right) {
                if(right == N) {
                    memset(temp, 0, sizeof temp);
                    for(int i = 0; i < row; ++i)
                        temp[i] += M[i][N - 1];
                }
                for(int i = 0; i < row; ++i)
                    temp[i] += M[i][right];

                maxSum = max(maxSum, kadane());
            }
        }
        printf("%d\n", maxSum);
    }
    return 0;
}
*/