Submission #1030364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030364		caterpillow	Bomb (IZhO17_bomb)	C++17	29 / 100	1076 ms	33288 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'

/*

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;
    // check if possible
    // F0R (r, rs - h + 1) {
    //     F0R (c, cs) {
    //         int s = sum(r, c, r + h - 1, c);
    //         if (0 < s && s < h) return 0;
    //     }
    // }

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

    // F0R (r, rs - h + 1) {
    //     F0R (c, cs) {
    //         cerr << mod[r][c] << " \n"[c == cs - 1];
    //     }
    // }

    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;
            }
        }
        if (streak) mn = min(mn, streak);
    }
    return mn;
}

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

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

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

    // F0R (r, rs) {
    //     F0R (c, cs) {
    //         cerr << grid[r][c] << " \n"[c == cs - 1];
    //     }
    // }

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

Compilation message (stderr)

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

• Subtask 1: 29 / 100