Submission #171766

#	Time	Username	Problem	Language	Result	Execution time	Memory
171766		mosiashvililuka	Bomb (IZhO17_bomb)	C++14	24 / 100	50 ms	12796 KiB

bomb

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,dp[2509][2509],zx,xc,qw,we,k[2509][2509],pas,dd,mxa,mxb;
string s;
bool f[2509][2509];
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    for(c=1; c<=a; c++){
        cin>>s;
        for(d=1; d<=b; d++){
            f[c][d]=s[d-1]-'0';
        }
    }
    mxb=mxa=a+b+2;
        for(c=1; c<=a; c++){
        	zx=0;
        	for(d=1; d<=b; d++){
        		if(f[c][d]==1){
        			zx++;
				}else{
				    if(zx!=0) mxa=min(zx,mxa);
					zx=0;
				}
			}
			if(zx!=0) mxa=min(zx,mxa);
		}
		for(d=1; d<=b; d++){
			xc=0;
			for(c=1; c<=a; c++){
				if(f[c][d]==1){
					xc++;
				}else{
				    if(xc!=0) mxb=min(mxb,xc);
					xc=0;
				}
			}
			if(xc!=0) mxb=min(mxb,xc);
		}
		cout<<mxa*mxb;
        return 0;
    for(c=1; c<=a; c++){
        for(d=1; d<=b; d++) dp[c][d]=dp[c-1][d]+dp[c][d-1]-dp[c-1][d-1]+f[c][d];
    }
    d=b;
    for(c=1; c<=a; c++){
        while(d>=1){
            bool bo=0;
            for(i=1; i<=a; i++) for(j=1; j<=b; j++) k[i][j]=0;
            for(i=c; i<=a; i++){
                for(j=d; j<=b; j++){
                    qw=i-c+1;we=j-d+1;
                    if(dp[i][j]-dp[i][we-1]-dp[qw-1][j]+dp[qw-1][we-1]==c*d){
                        k[qw][we]=1;
                    }
                }
            }
/*            if(c==2&&d==2){
                for(i=1; i<=a; i++){
                    for(j=1; j<=b; j++) cout<<k[i][j]<<" ";
                    cout<<endl;
                }
            }
            if(c==2&&d==2) cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl;*/
            for(i=1; i<=a; i++){
                for(j=1; j<=b; j++) k[i][j]=k[i-1][j]+k[i][j-1]-k[i-1][j-1]+k[i][j];
            }
/*            if(c==2&&d==2){
                for(i=1; i<=a; i++){
                    for(j=1; j<=b; j++) cout<<k[i][j]<<" ";
                    cout<<endl;
                }
            }*/
            for(i=1; i<=a; i++){
                if(bo==1) break;
                for(j=1; j<=b; j++){
                    if(f[i][j]==0) continue;
                    qw=i-c+1;we=j-d+1;
                    if(qw<=0) qw=1;
                    if(we<=0) we=1;
                    int hj=0;
                    hj=k[i][j]-k[qw-1][j]-k[i][we-1]+k[qw-1][we-1];
                    if(hj==0){
                        bo=1;
                        break;
                    }
                }
            }
            if(bo==0){
//                cout<<c<<" "<<d<<" vict"<<endl;
                if(pas<c*d) pas=c*d;
                break;
            }
  //          cout<<c<<" "<<d<<" lose"<<endl;
            d--;
        }
    }
    cout<<pas;
    return 0;
}

• Subtask 1: 24 / 100