Submission #334197

#	Time	Username	Problem	Language	Result	Execution time	Memory
334197		juggernaut	Bomb (IZhO17_bomb)	C++14	21 / 100	355 ms	31212 KiB

bomb

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt[2505][2505],pref[2505][2505],mx;
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));
}
void add(int x,int y,int x2,int y2){
    x2++,y2++;
    pref[x][y]++;
    pref[x2][y2]++;
    pref[x][y2]--;
    pref[x2][y]--;
}
clock_t start;
bool check(int x,int y){
    if(clock()-start>2000){
        printf("%d",mx);
        exit(0);
    }
    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))
                add(i,j,i+x-1,j+y-1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            pref[i][j]=pref[i][j]-pref[i-1][j-1]+pref[i][j-1]+pref[i-1][j];
            if(a[i][j]&&!pref[i][j])return false;
        }
    return true;
}
int main(){
    start=clock();
    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];
        }
    int y=1,x=n;
    for(;y<=m;y++){
        while(x&&!check(x,y))x--;
        mx=max(mx,x*y);
    }
    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:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 21 / 100