ABC005 D -おいしいたこ焼きの焼き方

atcoder.jp

問題文を誤読していたりしてバグり散らかしましたがなんとかAC.
がりがりの探索でTLEが心配でしたが実行時間5sec！に助けられて間に合いました。
高速で通している人も多いのでもっと工夫はできそうです。

二次元累積和の考え方もだいぶ定着。
けんちょんさんの記事（
累積和を何も考えずに書けるようにする！ - Qiita
）で初めて見たときは天才かと思いました。

累積和をとるときから二次元で累積するのが要注意です。

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

int N;
int D[51][51];
int AD[51][51];

int uma(int x) {
  int re = -250000;
  int er=0;

  for(int k=1;k<=N;k++){
    for(int l=1;l<=N;l++){
      if(k*l > x) continue;   
      for (int i = k; i <= N; i++) {
		for (int j = l; j <= N; j++) {
			er = AD[i][j] - AD[i][j-l] - AD[i-k][j] + AD[i-k][j-l];
          re=max(er,re);
        }
      }
    }
  }
  return re;
}

int main() {
	cin >> N;
	
	//入力　位置別おいしさ指数
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin>>D[i][j];
		}
	}

	//累積和計算
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			AD[i][j] = AD[i-1][j] + AD[i][j-1]+D[i][j]-AD[i-1][j-1];
		}
	}
  int Q;
  cin >> Q;
  int p;
  for (int i = 0; i < Q; i++) {
    cin>>p;
    cout << uma(p) << endl;
  }
  return 0;
}