POJ(PKU) 1050 To the Max

解法：ナイーブな実装.O(N^4).

O(N^4)になるのでダメ、といっているものを拝見しましたが、実はO(N^4)でいけます。（ちょっと工夫が必要だけど

累積和を二次元にするだけです。
難しく考えすぎるとかえってダメな場合もありますね、、、。

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
  
  int n,k[102][102]={0},ans = -100000000;
  
  scanf("%d",&n);
  
  for(int i = 1;i <= n;i++){
    for(int j = 1;j <= n;j++){
      int tmp;
      scanf("%d",&tmp);
      k[i][j] = k[i][j-1] + k[i-1][j] - k[i-1][j-1] + tmp;
    }
  }
  
  for(int i = 1;i <= n;i++){
    for(int j = i;j <= n;j++){
      for(int l = 1;l <= n;l++){
	for(int m = l;m <= n;m++){
	  ans = max(ans,k[m][j]-k[l-1][j]-k[m][i-1]+k[l-1][i-1]);
	}
      }
    }
  }
  
  printf("%d\n",ans);
  
  return 0;
}