제출 #523092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523092		dostigator	Bomb (IZhO17_bomb)	C++17	0 / 100	1103 ms	12620 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=mod;
    if(n==1 || m==1){
        if(n==1){
            for(int i=1; i<=m; ++i){
                dp[i]=dp[i-1];
                if(a[1][i]=='1')dp[i]++;
                if(dp[i]) ans=min(ans,dp[i]);
            }
            if(ans==mod){
                cout<<0<<endl;
                return;
            }
            cout<<ans<<endl;
        }
        if(m==1){
            for(int i=1; i<=n; ++i){
                dp[i]=dp[i-1];
                if(a[i][1]=='1')dp[i]++;
                if(dp[i]) ans=min(ans,dp[i]);
            }
            if(ans==mod){
                cout<<0<<endl;
                return;
            }
            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: 0 / 100