Submission #334311

#	Time	Username	Problem	Language	Result	Execution time	Memory
334311		juggernaut	Bomb (IZhO17_bomb)	C++14	100 / 100	721 ms	55648 KiB

bomb

#include<bits/stdc++.h>
using namespace std;
template<class T>void umin(T& a,T b){if(b<a)a=b;}
template<class T>void umax(T& a,T b){if(b>a)a=b;}
int n,m,xx,yy,up[2505][2505],down[2505][2505],ans[2505];
bool ar[2505][2505];
char rd(){
    char ch;
    do{
        scanf("%c",&ch);
    }while(ch!='0'&&ch!='1');
    return ch;
}
int main(){
    scanf("%d%d",&n,&m);
    xx=n,yy=m;
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=1;j<=m;j++){
            ar[i][j]=(rd()=='1');
            if(ar[i][j])cnt++;
            else{
                if(cnt)umin(yy,cnt);
                cnt=0;
            }
        }
        if(cnt)umin(yy,cnt);
    }
    for(int j=1;j<=m;j++){
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(ar[i][j]){
                cnt++;
                up[i][j]=up[i-1][j]+1;
            }else{
                if(cnt)umin(xx,cnt);
                cnt=0;
            }
        }
        if(cnt)umin(xx,cnt);
        for(int i=n;i>0;i--)if(ar[i][j])down[i][j]=down[i+1][j]+1;
    }
    for(int i=1;i<=yy;i++)ans[i]=xx;
    for(int i=1;i<=n;i++){
        int cnt=0;
        int a=2e9,b=2e9;
        for(int j=1;j<=m;j++){
			if(ar[i][j]){
				umin(a,up[i][j]);
				umin(b,down[i][j]);
				umin(ans[++cnt],a+b-1);
			}else{
			    cnt=0;
			    a=b=2e9;
			}
		}
		cnt=0;
        a=2e9,b=2e9;
        for(int j=m;j>0;j--){
			if(ar[i][j]){
				umin(a,up[i][j]);
				umin(b,down[i][j]);
				umin(ans[++cnt],a+b-1);
			}else{
			    cnt=0;
			    a=b=2e9;
			}
		}
    }
    int res=ans[1];
	for(int i=2;i<=yy;i++){
		umin(ans[i],ans[i-1]);
		umax(res,i*ans[i]);
	}
	printf("%d",res);
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100