Submission #869705

#	Time	Username	Problem	Language	Result	Execution time	Memory
869705		hentai_lover	Bomb (IZhO17_bomb)	C++14	0 / 100	1104 ms	21960 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pb push_back
#define fr(i, l, r) for(ll i = l; i <= r; ++ i)
#define rf(i, l, r) for(ll i = l; i >= r; -- i)

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef int ll;
typedef pair<ll, ll> pll;

const ll oo = ll(1e9) + 10;

ll p[3000][300];

ll get(ll x1, ll y1, ll x2, ll y2){
    return p[x2][y2] - p[x2][y1 - 1] - p[x1 - 1][y2] + p[x1 - 1][y1 - 1];
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m, ansx = 0, ansy = 0, ans = 0;
    cin >> n >> m;
    //if(n * m > 10000)return 0;
    char a[n + 1][m + 1];
    fr(i, 1, n)fr(j, 1, m){
        cin >> a[i][j];
        p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + 1 - (a[i][j] - '0');
    }
    rf(r, n, 1){
        rf(c, m, 1){
            vector <pll> v;
            fr(i, 1, n - r + 1){
                fr(j, 1, m - c + 1){
                    //if(a[i][j] == '0')continue;
                    //cout << "i = " << i << " j = " << j << " get = " << get(i, j, i + r - 1, j + c - 1) << endl;
                    if(get(i, j, i + r - 1, j + c - 1) == 0)v.pb({i, j});
                }
            }
            reverse(v.begin(), v.end());
            //cout << "r = " << r << " c = " << c << endl;
            //cout << "v: " << endl;
            //for(auto i : v)cout << i.first << ' ' << i.second << endl;
            bool usd[n + 1][m + 1];
            fr(i, 1, n)fr(j, 1, m)usd[i][j] = 0;
            for(auto x : v){
                fr(i, 0, r - 1){
                    if(usd[x.first + i][x.second])break;
                    fr(j, 0, c - 1){
                        if(usd[x.first + i][x.second + j])break;
                        usd[x.first + i][x.second + j] = 1;
                    }
                }
            }

            bool ok = 1;
            fr(i, 1, n){
                fr(j, 1, m){
                    if(a[i][j] == '1' && usd[i][j] == 0)ok = 0;
                }
            }
            if(ok)ans = max(ans, r * c);
        }
    }
    //cout << ansx << ' ' << ansy << endl;


    ansx = oo, ansy = oo;

    fr(i, 1, n){
        fr(j, 1, m){
            if(a[i][j] == '0')continue;
            ll l = -1, r = -1, u = -1, d = -1;
            fr(x, i, n){
                if(a[x][j] == '0')break;
                r = x;
            }
            if(r < 0)r = n;
            rf(x, i, 1){
                if(a[x][j] == '0')break;
                l = x;
            }
            if(l < 0)l = 1;
            fr(x, j, m){
                if(a[i][x] == '0')break;
                d = x;
            }
            if(d < 0)d = m;
            rf(x, j, 1){
                //cout << "u = " << u << " i = " << i << " x = " << x << " a[i][x] = " << a[i][x] << endl;
                if(a[i][x] == '0')break;
                u = x;
            }
            if(u < 0)u = 1;


            ll a = r - l + 1;
            ll b = d - u + 1;
            //cout << "i = " << i << " j = " << j << "a = " << a << " b = " << b << " u = " << u << " d = " << d << endl;
            ansx = min(ansx, a);
            ansy = min(ansy, b);
        }
    }
    //cout << ansx << ' ' << ansy << endl;

    cout << ans;
    if(ans > ansx * ansy)cout<<1/0;
    cout << ansx * ansy << endl;
}


/*
3 3
011
111
111
*/

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:116:33: warning: division by zero [-Wdiv-by-zero]
  116 |     if(ans > ansx * ansy)cout<<1/0;
      |                                ~^~

• Subtask 1: 0 / 100