제출 #1030382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030382		caterpillow	Bomb (IZhO17_bomb)	C++17	29 / 100	1090 ms	2412 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define vt vector
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b)  for (int i = (a); i < (b); i++)
#define F0R(i, b) FOR(i, 0, b)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define pb push_back
#define endl '\n'

#ifndef LOCAL
#define cerr if (0) std::cerr
#endif

/*

N^3: find max width for each given height

*/

int rs, cs;
vt<vt<bool>> grid;
vt<vt<int>> sfx;

int sum(int r1, int c1, int r2, int c2) {
    r2 = min(r2, rs - 1);
    c2 = min(c2, cs - 1);
    return sfx[r1][c1] - sfx[r1][c2 + 1] - sfx[r2 + 1][c1] + sfx[r2 + 1][c2 + 1];
}

main() {
    cin.tie(0)->sync_with_stdio();

    cin >> rs >> cs;
    if (rs > 450 || cs > 450) return 0;
    rs += 2, cs += 2;
    grid.resize(rs, vt<bool>(cs));
    sfx.resize(rs + 1, vt<int>(cs + 1));
    FOR (r, 1, rs - 1) {
        FOR (c, 1, cs - 1) {
            char ch; cin >> ch;
            grid[r][c] = sfx[r][c] = ch - '0';
        }
    }
    ROF (r, 0, rs) ROF (c, 0, cs) sfx[r][c] += sfx[r][c + 1];
    ROF (r, 0, rs) ROF (c, 0, cs) sfx[r][c] += sfx[r + 1][c];

    int mxw = cs, mxh = rs;
    F0R (r, rs) {
        int streak = 0;
        F0R (c, cs) {
            if (grid[r][c]) streak++;
            else if (streak) mxw = min(mxw, streak), streak = 0;
        }
    }
    F0R (c, cs) {
        int streak = 0;
        F0R (r, rs) {
            if (grid[r][c]) streak++;
            else if (streak) mxh = min(mxh, streak), streak = 0;
        }
    }

    cerr << mxw << " " << mxh << endl;

    int best = 0;
    FOR (h, 1, mxh + 1) {
        FOR (w, 1, mxw + 1) {
            vt<vt<int>> pfx(rs, vt<int>(cs));
            auto is_covered = [&] (int r, int c) {
                return (pfx[r][c] - (r - h >= 0 ? pfx[r - h][c] : 0) - (c - w >= 0 ? pfx[r][c - w] : 0) + (r - h >= 0 && c - w >= 0 ? pfx[r - h][c - w] : 0)) > 0;
            };
            auto add = [&] (int r, int c) {
                pfx[r][c] += (r ? pfx[r - 1][c] : 0) + (c ? pfx[r][c - 1] : 0) - (r && c ? pfx[r - 1][c - 1] : 0);
            };

            cerr << w << " " << h << endl;

            bool good = true;
            F0R (r, rs - 1) {
                F0R (c, cs - 1) {
                    if (sum(r, c, r + h - 1, c + w - 1) == w * h) {
                        pfx[r][c]++;
                    }
                    add(r, c);
                    if (grid[r][c] == 1) {
                        cerr << is_covered(r, c) << endl;
                        good &= is_covered(r, c);
                    }
                }
            }
            if (good) best = max(best, w * h);
        }
    }
    cout << best << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~
bomb.cpp: In function 'int main()':
bomb.cpp:47:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   47 |             grid[r][c] = sfx[r][c] = ch - '0';

• Subtask 1: 29 / 100