10827 - Maximum sum on a torus

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (ll i = a; i < b; ++i)
#define REP(i,a,b) for (ll i = a; i <= b; ++i)
#define INF 9999999999
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t; cin >> t; while (t--)
    {
        ll n, mx=0, tmp; cin >> n; ll dp[2*n+1][2*n+1];
        REP(i,0,n) dp[0][i]=dp[i][0]=0;
        REP(i,1,n) REP(j,1,n) cin >> tmp, dp[i][j]=dp[i+n][j]=dp[i][j+n]=dp[i+n][j+n]=tmp;
        REP(i,1,2*n) REP(j,1,2*n) dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j];
        REP(i,1,n) REP(j,1,n) REP(p,i,i+n-1) REP(q,j,j+n-1) mx=max(mx,dp[p][q]-(dp[i-1][q]+dp[p][j-1]-dp[i-1][j-1]));
        cout << mx << endl;
    }
}