Submission #167064

#	Time	Username	Problem	Language	Result	Execution time	Memory
167064		hentai_lover	Bomb (IZhO17_bomb)	C++14	14 / 100	171 ms	760 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;

int main() {
    //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m, ansx = oo, ansy = oo;
    cin >> n >> m;
    if(min(n, m) > 500)return 0;
    char a[n + 1][m + 1];
    fr(i, 1, n)fr(j, 1, m)cin >> a[i][j];

    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 << ansx * ansy << endl;
}


/*
3 3
1 5 1
2 3
1 3 5
2 3
*/

• Subtask 1: 14 / 100