Submission #343854

#	Time	Username	Problem	Language	Result	Execution time	Memory
343854		topovik	Bomb (IZhO17_bomb)	C++14	21 / 100	99 ms	65924 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define f first
#define s second
#define pb push_back
#define INF 1000000000

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const ll N = 3e3;

const ll oo = 1e10;

ll pr[N][N];
ll n, m;

ll sum(ll sx, ll sy, ll ex, ll ey)
{
    return pr[ex][ey] - pr[sx - 1][ey] - pr[ex][sy - 1] + pr[sx - 1][sy - 1];
}

ll Check(ll width, ll x, ll y)
{
    ll sy = y - width;
    ll lx = 1, rx = x;
    while (lx < rx)
    {
        ll mdl = (lx + rx) >> 1;
        if (sum(mdl, sy, x, y) != (x - mdl + 1) * (width + 1)) lx = mdl + 1;
        else rx = mdl;
    }
    ll sx = lx;
    lx = x, rx = n;
    while (lx < rx)
    {
        ll mdl = (lx + rx + 1) >> 1;
        if (sum(x, sy, mdl, y) != (mdl - x + 1) * (width + 1)) rx = mdl - 1;
        else lx = mdl;
    }
    ll ex = lx;
    return ex - sx + 1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    string a[n];
    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= m; j++) pr[i][j] = pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1] + (a[i - 1][j - 1] == '1');
    ll ansx = oo, ansy = oo;
    for (ll i = 0; i < n; i++)
    {
        ll group = -oo;
        if (a[i][0] == '1') group = 0;
        for (ll j = 1; j < m; j++)
            if (a[i][j] == '1')
        {
            if (a[i][j - 1] == '1') group++;
            else                    group = 0;
        }
        else
        {
            if (group != -oo)
            {
                ll x = Check(group, i + 1, j);
                ansx = min(ansx, group + 1);
                ansy = min(ansy, x);
            }
            group = -oo;
        }
        if (group != -oo)
        {
            ll x = Check(group, i + 1, m);
            ansx = min(ansx, group + 1);
            ansy = min(ansy, x);
        }
    }
    if (ansx == oo) cout << 0 << endl;
    else cout << ansx * ansy;
}

• Subtask 1: 21 / 100