[AtCoder] ABC 005 D – おいしいたこ焼きの焼き方

2020年9月22日2020年12月12日

問題

方針

長方形の和は二次元の累積和を使うことで高速に求めることができるので、全ての長方形のパターンを計算し、\( i \) 個のたこ焼きを焼くときの最大値 \( d(i) \) を求めます。\( d(j) > d(i) \ (j < i)\) となる可能性があることに注意します。

コード

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

ll S[51][51]{};
ll D[50][50];
int N;

void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            S[i + 1][j + 1] = D[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            S[i + 1][j + 1] += S[i + 1][j] + S[i][j + 1] - S[i][j];
        }
    }
}

ll get(int r1, int c1, int r2, int c2) {
    return S[r2][c2] + S[r1][c1] - S[r1][c2] - S[r2][c1];
}


int main() {
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> D[i][j];
        }
    }
    int Q;
    cin >> Q;
    int P[Q];
    for (int i = 0; i < Q; i++) {
        cin >> P[i];
    }
    init();
    ll d[N * N + 1]{};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = i + 1; k <= N; k++) {
                for (int l = j + 1; l <= N; l++) {
                    int t = (k - i) * (l - j);
                    d[t] = max(d[t], get(i, j, k, l));
                }
            }
        }
    }

    ll v = 0;
    for (int i = 1; i <= N * N; i++) {
        d[i] = max(v, d[i]);
        v = max(v, d[i]);
    }
    for (int i : P) {
        cout << d[i] << "\n";
    }
    return 0;
}

参考