提出 #18395415

---

ソースコード 拡げる

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

int calc_area(int i, int j, int k, int l, int64_t cumsum[126][126],
        int64_t K, int64_t V)
{
    int64_t v1 = cumsum[j + 1][l + 1];
    v1 -= cumsum[j + 1][k] + cumsum[i][l + 1];
    v1 += cumsum[i][k];
    int area = (j - i + 1) * (l - k + 1);
    int64_t v2 = v1 + K * area;
    if (v2 <= V)
        return area;
    else
        return -1;
}

int main()
{
    int64_t A_grid[125][125] = {0};
    int64_t cumsum[126][126] = {0};
    int H, W;
    int64_t K, V;
    cin >> H >> W >> K >> V;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j)
            cin >> A_grid[i][j];
    }
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            int64_t tmp = A_grid[i][j];
            tmp += cumsum[i + 1][j] + cumsum[i][j + 1];
            tmp -= cumsum[i][j];
            cumsum[i + 1][j + 1] = tmp;
        }
    }
    int64_t max_area = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = i; j < H; ++j) {
            for (int k = 0; k < W; ++k) {
                for (int l = k; l < W; ++l) {
                    int area = calc_area(i, j, k, l, cumsum, K, V);
                    if (max_area < area)
                        max_area = area;
                }
            }
        }
    }
    cout << max_area << endl;
}

提出情報

ジャッジ結果