Submission #442588

#	Time	Username	Problem	Language	Result	Execution time	Memory
442588		leaked	Bomb (IZhO17_bomb)	C++14	100 / 100	115 ms	80084 KiB

bomb

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define vec vector
#define sz(x) ( int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

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,32000),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 up[N][N],dn[N][N],n,m;
int a[N][N];
int tt;
int lst[N],mxm[N];
 int fck[N];
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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=1;i<=m;i++){
        mxm[i]=1e9;
    }
    for( int i=n;i>=1;i--){
        for( int j=m;j>=1;j--){
            if(a[i][j]) dn[i][j]=dn[i+1][j]+1;
        }
    }
    for( int i=1;i<=n;i++){
        for( int j=m;j>=1;j--){
            if(a[i][j]) up[i][j]=up[i-1][j]+1,umin(mxm[1],up[i][j]+dn[i][j]-1);;
        }
    }
    for(int rep=0;rep<2;rep++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!a[i][j]) continue;
            int r=j;
            while(a[i][r]) r++;
            int f=n,s=n;

            for(int k=1;k<=r-j;k++){
                umin(f,up[i][j+k-1]);
                umin(s,dn[i][j+k-1]);
//                cerr<<k<<' '<<f+s<<endl;
                umin(mxm[k],f+s-1);
            }
            umin(mxm[r-j+1],0);
            j=r;
        }
    }
    for(int i=1;i<=n;i++){
        reverse(up[i]+1,up[i]+m+1);
        reverse(dn[i]+1,dn[i]+m+1);
        reverse(a[i]+1,a[i]+m+1);
    }
    }
    for( int i=2;i<=m;i++) umin(mxm[i],mxm[i-1]);
    int ans=0;
    for( int i=1;i<=m;i++){
        umax(ans,i*mxm[i]);
    }
    cout<<ans;
    return 0;
}

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

• Subtask 1: 100 / 100