uva108 - max sum 2d

uva108.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }


const int maxn=105;
const int inf=(int)1e9;
int n;
int grid[maxn][maxn];
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  //cout << fixed << setprecision(6);
  cin>>n;
  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      cin>>grid[i][j];
    }
  }

  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      if (i>0) grid[i][j] += grid[i-1][j];
      if (j>0) grid[i][j] += grid[i][j-1];
      if (i>0 && j>0) grid[i][j] -= grid[i-1][j-1];
    }
  }

  int ans = -inf;
  for (int x1=0; x1<n; x1++) {
    for (int y1=0; y1<n; y1++) {
      for (int x2=x1; x2<n; x2++) {
	for (int y2=y1; y2<n; y2++) {
	  int cur = grid[x2][y2];
	  if (x1>0) cur -= grid[x1-1][y2];
	  if (y1>0) cur -= grid[x2][y1-1];
	  if (x1>0 && y1>0) cur += grid[x1-1][y1-1];
	  ans = max(ans, cur);
	}
      }
    }
  }
  cout<<ans<<endl;

  return 0;
}