[AtCoder] GigaCode 2019 D – 家の建設

2019年11月25日

問題

方針

二次元の累積和を利用して解きます。二次元の累積和を利用することで長方形の領域で表される土地の地価の和を \( O(1) \) で計算することができます。よって、全てのマスを全探索して求めます。計算量は、\( O(H^2W^2) \) となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int H, W;
    ll K, V;
    cin >> H >> W >> K >> V;
    ll A[H][W];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> A[i][j];
        }
    }
    ll B[H + 1][W + 1]{};
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            B[i + 1][j + 1] += A[i][j] + B[i + 1][j];
        }
    }
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            B[j + 1][i + 1] += B[j][i + 1];
        }
    }
    ll ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            for (int k = i + 1; k <= H; k++) {
                for (int l = j + 1; l <= W; l++) {
                    ll v = B[k][l] - B[i][l] - B[k][j] + B[i][j];
                    ll t = (k - i) * (l - j);
                    v += t * K;
                    if (v <= V) {
                        ans = max(ans, t);
                    }
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}