Submission #523099

#	Time	Username	Problem	Language	Result	Execution time	Memory
523099		dostigator	Bomb (IZhO17_bomb)	C++17	19 / 100	1100 ms	12560 KiB

bomb

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define IShowSpeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define popcnt __builtin_popcount
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mii map<int,int>
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define pb push_back
#define vt vector
#define endl '\n'
#define X first
#define Y second
typedef long double ld;
typedef long long ll;
const ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},N=1e6+10;
const ll mod=1e9+7,inf=1e18;
int dp[N];
void solve(){
    int n,m;
    cin>>n>>m;
    char a[n+2][m+2],c[n+2][m+2];
    for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) cin>>a[i][j];
    int ans=0,cnt=0;
    if(n==1){
        ans=mod;
		for(int i=1; i<=m; ++i) {
			if(a[1][i]=='1') ++cnt;
			else{
				if(cnt>0) ans=min(ans,cnt);
				cnt=0;
			}
		}
		if(a[1][m]=='1') ans=min(ans,cnt);
		cout<<ans<<endl;
		return;
	}
	if(m==1){
	    ans=mod;
		for(int i=1; i<=n; ++i){
			if(a[i][1]=='1') ++cnt;
			else{
				if(cnt>0) ans=min(ans,cnt);
				cnt=0;
			}
		}
		if(a[n][1]=='1') ans=min(ans,cnt);
		cout<<ans<<endl;
		return;
	}
    for(int x=1; x<=n; ++x){
        for(int y=1; y<=m; ++y){
            for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) c[i][j]=a[i][j];
            for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
                int bad=1;
                if(i+x-1>n || j+y-1>m) continue;
                for(int ol=i; ol<=i+x-1; ++ol) for(int zhas=j;  zhas<=j+y-1; ++zhas) if(c[ol][zhas]=='0') bad=0;
                if(bad) for(int ol=i; ol<=i+x-1; ++ol) for(int zhas=j;  zhas<=j+y-1; ++zhas) c[ol][zhas]='2';
            }
            int ok=1;
            for(int ol=1; ol<=n; ++ol) for(int zhas=1;  zhas<=m; ++zhas) if(c[ol][zhas]=='1')ok=0;
            if(ok)ans=max(ans,x*y);
        }
    }
    cout<<ans<<endl;
}
int main() {
    IShowSpeed;
    int tt=1;
    //cin>>tt;
    while(tt--) solve();
}

• Subtask 1: 19 / 100