Submission #333998

#	Time	Username	Problem	Language	Result	Execution time	Memory
333998		juggernaut	Bomb (IZhO17_bomb)	C++14	35 / 100	1101 ms	58724 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;
}
bool check_1(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=j;k<=j+y-1;k++)pref[i][k]++,pref[i+x][k]--;
            }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pref[i][j]+=pref[i-1][j];
            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];
        }
//    if(n<m){
//        for(int x=1;x<=m;x++){
//            int l=1,r=n;
//            while(l<r){
//                int mid=(l+r+1)>>1;
//                if(check(mid,x))l=mid;
//                else r=mid-1;
//            }
//            if(!check(l,x))l=0;
//            mx=max(mx,x*l);
//        }
//        printf("%d",mx);
//    }else{
        for(int x=1;x<=n;x++){
            int l=max(1,(mx+x-1)/x),r=m;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(check_1(x,mid))l=mid;
                else r=mid-1;
            }
            if(!check_1(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:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 35 / 100