Submission #920207

#	Time	Username	Problem	Language	Result	Execution time	Memory
920207		MilosMilutinovic	Bomb (IZhO17_bomb)	C++14	47 / 100	1038 ms	51548 KiB

bomb

// Online C++ compiler to run C++ program online
#include<bits/stdc++.h>

using namespace std;

int n,m;
char s[2505];
int v[2505][2505],a[2505][2505];
bool was[2505][2505];

int queryA(int x1,int y1,int x2,int y2){
    return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}

int queryV(int x1,int y1,int x2,int y2){
    return v[x2][y2]-v[x1-1][y2]-v[x2][y1-1]+v[x1-1][y1-1];
}

bool check(int x,int y){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v[i][j]=0;
        }
    }
    for(int i=1;i+x<=n+1;i++){
        for(int j=1;j+y<=m+1;j++){
            if(queryA(i,j,i+x-1,j+y-1)==x*y){
                v[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v[i][j]+=v[i-1][j];
            v[i][j]+=v[i][j-1];
            v[i][j]-=v[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(queryA(i,j,i,j)==1&&queryV(max(1,i-x+1),max(1,j-y+1),i,j)==0){
                return false;
            }
        }
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            a[i][j]=(int)(s[j]-'0');
            a[i][j]+=a[i-1][j];
            a[i][j]+=a[i][j-1];
            a[i][j]-=a[i-1][j-1];
        }
    }
    int lx=n;
    int ly=m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(queryA(i,j,i,j)==0) continue;
            int ptr=j;
            while(ptr+1<=m&&queryA(i,ptr+1,i,ptr+1)==1) ptr++;
            ly=min(ly,ptr-j+1);
            j=ptr;
        }
    }
    for(int j=1;j<=m;j++){ 
        for(int i=1;i<=n;i++){
            if(queryA(i,j,i,j)==0) continue;
            int ptr=i;
            while(ptr+1<=n&&queryA(ptr+1,j,ptr+1,j)==1) ptr++;
            lx=min(lx,ptr-i+1);
            i=ptr;
        }
    }
    int ans=0;
    for(int x=lx;x>=1;x--){
        int l=1,r=ly;
        while(l<=r){
            int mid=(l+r)/2;
            if(x*mid<=ans||check(x,mid)) ans=max(ans,x*mid),l=mid+1; else r=mid-1;
        }
        int low=1,high=x-1,nxt=0;
        while(low<=high){
            int mid=(low+high)/2;
            if((ans+mid)/mid<=ly&&check(mid,(ans+mid)/mid)) nxt=mid,low=mid+1; else high=mid-1;
        }
        x=nxt;
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 47 / 100