#DP #MIS #MIS2D #UVa #Solved

10827 - Maximum sum on a torus.cpp

//https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1768
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int dp[155][155];
int n, m, t, x;

int main() {
    cin>>t;
    while(t--) {
        cin>>n;
        lp(i, n) {
            lp(j, n) {
                cin>>x;
                dp[i+1+n][j+1] = dp[i+1][j+1] = x + dp[i+1][j];

            }
        }
        lp(i, n) lp(j, n) {
             dp[i+1][j+1+n] = dp[i+1+n][j+1+n] = dp[i+1][j+1] + dp[i+1][n];
        }

    //lp(i, 2*n){ lp(j, 2*n) cout << dp[i+1][j+1] << " "; cout << endl;}

    int sum = 0, best = 0, bestOfBest = 0, n2 = n*2;
    for(int i = 1; i<=n; i++) {
        for(int j = i; j <= i+n-1 ; j++) {
            sum = 0;
            for(int h = 1; h <= n; h++, sum = 0)
                for(int k = h; k <= h+n-1; k++) {
                    x = dp[k][j] - dp[k][i-1];
                    if(sum < 0 ) sum = x;
                    else sum += x;
                    if(sum > best) best = sum;
                }
            if(best > bestOfBest) bestOfBest = best;
        }
    }
    cout << bestOfBest << endl;
    }
    return 0;
}