Submission #333918

#	Time	Username	Problem	Language	Result	Execution time	Memory
333918		juggernaut	Bomb (IZhO17_bomb)	C++14	32 / 100	1103 ms	55660 KiB

bomb

#include<bits/stdc++.h>
using namespace std;
int n,m,mx,cnt[2505][2505],pref[2505][2505];
bool a[2505][2505];
char rd(){
    char ch;
    do{
        scanf("%c",&ch);
    }while(ch!='0'&&ch!='1');
    return ch;
}
bool sum(int x,int y,int x2,int y2){
    return (cnt[x2][y2]-cnt[x2][y-1]-cnt[x-1][y2]+cnt[x-1][y-1])==((x2-x+1)*(y2-y+1));
}
bool check(int x,int y){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)pref[i][j]=0;
    for(int i=1;i+x-1<=n;i++)
        for(int j=1;j+y-1<=m;j++)
            if(sum(i,j,i+x-1,j+y-1)){
                for(int k=i;k<=i+x-1;k++)pref[k][j]++,pref[k][j+y]--;
            }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pref[i][j]+=pref[i][j-1];
            if(a[i][j]&&!pref[i][j])return false;
        }
    }
    return true;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            a[i][j]=(rd()=='1');
            cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+a[i][j];
        }
    for(int x=1;x<=n;x++){
        int l=1,r=m;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(check(x,mid))l=mid;
            else r=mid-1;
        }
        if(!check(x,l))l=0;
        mx=max(mx,x*l);
    }
    printf("%d",mx);
}

Compilation message (stderr)

bomb.cpp: In function 'char rd()':
bomb.cpp:8:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |         scanf("%c",&ch);
      |         ~~~~~^~~~~~~~~~
bomb.cpp: In function 'int main()':
bomb.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 32 / 100