Submission #1030368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030368		caterpillow	Bomb (IZhO17_bomb)	C++17	18 / 100	114 ms	1312 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) {
    return sfx[r1][c1] - sfx[r1][c2 + 1] - sfx[r2 + 1][c1] + sfx[r2 + 1][c2 + 1];
}

int mx(int h) {
    cerr << "\nchecking " << h << endl;

    // find longest run
    vt<vt<bool>> mod(rs - h + 1, vt<bool>(cs));
    F0R (r, rs - h + 1) {
        F0R (c, cs) {
            mod[r][c] = sum(r, c, r + h - 1, c) == h;
        }
    }

    int mn = cs;
    F0R (r, rs - h + 1) {
        int streak = 0;
        F0R (c, cs) {
            if (mod[r][c]) streak++;
            else if (streak) mn = min(mn, streak), streak = 0;
        }
    }
    return mn;
}

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

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

    cerr << "maximum height " << mxh << endl;

    int ans = 0;
    FOR (h, 1, mxh + 1) {
        ans = max(ans, h * mx(h));
    }
    cout << ans << endl;
}

Compilation message (stderr)

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

• Subtask 1: 18 / 100