Submission #1230758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230758		Double_Slash	Bomb (IZhO17_bomb)	C++20	12 / 100	1 ms	1096 KiB

bomb

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

int n, m, ps[2501][2501];
bool grid[2501][2501];

int main() {
    cin >> n >> m;
    assert(max(n, m) <= 100);
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            char x;
            cin >> x;
            grid[r][c] = x == '1';
            ps[r + 1][c + 1] = ps[r][c + 1] + ps[r + 1][c] - ps[r][c] + grid[r][c];
        }
    }
    // cerr << n << ' ' << m << endl;
    // for (int r = 0; r < n; ++r) {
    //     for (int c = 0; c < m; ++c) {
    //         cerr << grid[r][c];
    //     }
    //     cerr << endl;
    // }
    auto can = [&] (int R, int C) {
        if (not (R * C)) return true;
        for (int r = n; r--;) {
            for (int c = m; c--;) {
                if (not grid[r][c]) continue;
                // cerr << r << ' ' << c << endl;
                if (not grid[r + 1][c] and not grid[r][c + 1]) {
                    if (r < R - 1 or c < C - 1) return false;
                    if (ps[r + 1][c + 1] - ps[r - R + 1][c + 1] - ps[r + 1][c - C + 1] + ps[r - R + 1][c - C + 1] < R * C) {
                        return false;
                    }
                } else if (not grid[r + 1][c]) {
                    if (r < R - 1) return false;
                    if (ps[r + 1][c + 1] - ps[r + 1][c] - ps[r - R + 1][c + 1] + ps[r - R + 1][c] < R) {
                        return false;
                    }
                } else if (not grid[r][c + 1]) {
                    if (c < C - 1) return false;
                    if (ps[r + 1][c + 1] - ps[r][c + 1] - ps[r + 1][c - C + 1] + ps[r][c - C + 1] < C) {
                        return false;
                    }
                }
            }
        }
        return true;
    };
    // cerr << can(3, 1);
    int ans = 0;
    for (int R = 1, C = m; R <= n; ++R) {
        while (not can(R, C)) --C;
        ans = max(ans, R * C);
    }
    cout << ans;
}

• Subtask 1: 12 / 100