AtCoder Beginner Contest 005 D - おいしいたこ焼きの焼き方

かみぺさんがまとめていたので解いてみることにしました。
良問，教育的問題リスト - Google スプレッドシート

問題

abc005.contest.atcoder.jp

解法

各クエリごとに計算するのではなく, データが与えられた時点で計算して, 各クエリには前計算した値でそのまま答えを書くだけにします。

では長方形のエリア内での最大値はどうやって求めるかというと, 基本的には「上端　下端　左端　右端」を全探索します。その長方形内の美味しさの合計はよくあるテクニックでがんばります。

const int MAXN = 55;
int D[MAXN][MAXN];
int sum[MAXN][MAXN];
int ans[MAXN*MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    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++) {
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + D[i][j];
    }
    for (int y1 = 1; y1 <= N; y1++) for (int y2 = y1; y2 <= N; y2++) {
        for (int x1 = 1; x1 <= N; x1++) for (int x2 = x1; x2 <= N; x2++) {
            int total = sum[y2][x2] - sum[y2][x1-1] - sum[y1-1][x2] + sum[y1-1][x1-1];
            int area = (y2-y1+1)*(x2-x1+1);
            ans[area] = max(ans[area], total);
        }
    }
    for (int i = 1; i <= N*N; i++) {
        ans[i] = max(ans[i], ans[i-1]);
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int p;
        cin >> p;
        cout << ans[p] << endl;
    }
    return 0;
}