Submission #333999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333999	2020-12-08T05:18:03 Z	juggernaut	Bomb (IZhO17_bomb)	C++14	Compilation error	0 ms	0 KB

bomb

#include<bits/stdc++.h>
using namespace std;
int n,m,mx,cnt[2505][2505],pref[2505][2505];
bool a[2505][2505];
char s[2505];
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);
    gets(s);
    for(int i=1;i<=n;i++){
        gets(s);
        for(int j=1;j<=m;j++){
            a[i][j]=(s[j-1]=='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

bomb.cpp: In function 'int main()':
bomb.cpp:43:5: error: 'gets' was not declared in this scope; did you mean 'fgets'?
   43 |     gets(s);
      |     ^~~~
      |     fgets
bomb.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~