Submission #441813

#	Time	Username	Problem	Language	Result	Execution time	Memory
441813		leaked	Bomb (IZhO17_bomb)	C++14	0 / 100	1 ms	348 KiB

bomb

#include <bits/stdc++.h>

#define vec vector
#define sz(x) (int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=2503;
int dp[N][N];
int a[N][N];
int n,m;
int check(int x){
    vec<vec<int>>lol(n+2,vec<int>(m+2,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dp[i][j]>=x){
                lol[i][j]++;lol[i][j+x]--;
                lol[i+x][j]--;
                lol[i+x][j+x]++;
            }
        }
    }
    int ok=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
//            cerr<<lol[i][j]<<' ';
            lol[i][j]+=lol[i-1][j]+lol[i][j-1]-lol[i-1][j-1];
//            cerr<<lol[i][j]<<' ';
            if(a[i][j]){
                ok&=(lol[i][j]>0);
//                if(!lol[i][j]){
//                    cout<<
//                }
            }

//            cout<<endl;
        }
//        cout<<endl;
    }
    return ok;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ifstream cin("bomb.in");
    ofstream cout("bomb.out");
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            a[i][j+1]=s[j]-'0';
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            if(a[i][j]){
                dp[i][j]=min({dp[i+1][j],dp[i][j+1],dp[i+1][j+1]})+1;
            }
        }
    }
//    cout<<check(2);
//    return 0;
    int l=1,r=min(n,m)+1;
    while(l!=r){
        int tm=(l+r)>>1;
        if(check(tm)) l=tm+1;
        else r=tm;
    }
    l--;
//    cout<<l<<endl;
//    return 0;
    int f=l,s=l;
    int o=2e9;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=(dp[i][j]>=l);
//            cerr<<dp[i][j]<<' ';
//            if(i==8 && j==11){
//                cout<<dp[i][j]<<endl;
//            }
        }
//        cerr<<endl;
    }
//    return 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!a[i][j]) continue;
            int k=j;
            while(k<=m && a[i][k]){
                k++;
            }
//            if(k-j-1==0){
//                cout<<i<<' '<<j<<endl;
//            }
            umin(o,k-j-1);
            j=k;
        }
    }
//    cout<<o<<endl;
    s+=o;
    o=2e9;
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            if(!a[i][j]) continue;
            int k=i;
            while(k<=n && a[k][j]){
                k++;
            }
            umin(o,k-i-1);
//            if(k-i-1==0){
//                cout<<i<<' '<<j<<endl;
//            }
//            cout<<k-i-1<<endl;
            i=k;
//            cerr<<k-i-1<<endl;
        }
    }
    f+=o;
    cout<<1ll*f*s;
    return 0;
}

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

• Subtask 1: 0 / 100