제출 #1030388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030388		caterpillow	Bomb (IZhO17_bomb)	C++17	42 / 100	1105 ms	56984 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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];
}

bool check(int w, int h) {
    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);
    };

    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) {
                if (!is_covered(r, c)) return false;
            }
        }
    }
    return true;
}

int solve(int mnh, int mxh, int mnw, int mxw) {
    if (mxh < mnh || mxw < mnw) return 0;
    int h = (mnh + mxh) / 2;
    int lo = mnw - 1, hi = mxw + 1;
    while (hi - lo > 1) {
        int w = (lo + hi) / 2;
        if (check(w, h)) lo = w;
        else hi = w;
    }
    return max({h * lo, solve(mnh, h - 1, lo, mxw), solve(h + 1, mxh, mnw, lo)});
}

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

    cin >> rs >> cs;
    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;

    cout << solve(1, mxh, 1, mxw) << endl;
}

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

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

• Subtask 1: 42 / 100