UVa10827

UVa10827
4つ繋げて循環させると簡単。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()

typedef long long int lli;

using namespace std;

const int N = (75 + 1) * 2;
int g[N][N];

int s[N][N];

void calc_sum(int n)
{
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      g[i][j + n] = g[i][j];
      g[i + n][j] = g[i][j];
      g[i + n][j + n] = g[i][j];
    }
  }
  n *= 2;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      s[i][j] = 0;
      for (int k = 0; k < i; ++k) {
        for (int l = 0; l < j; ++l) {
          s[i][j] += g[k][l];
        }
      }
    }
  }
  return ;
}

int get_sum(int n, int i1, int j1, int i2, int j2)
{
  return s[i2][j2] + s[i1][j1] - s[i2][j1] - s[i1][j2];
}

int solve(int n)
{
  int mx = -100;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k <= n; ++k) {
        for (int l = 0; l <= n; ++l) {
          mx = max(mx, get_sum(n, i, j, i + k, j + l));
        }
      }
    }
  }
  return mx;
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cin >> g[i][j];
      }
    }
    calc_sum(n);
    cout << solve(n) << endl;    
  }
  return 0;
}
-