Submission #37651

#	Time	Username	Problem	Language	Result	Execution time	Memory
37651		Kerim	Bomb (IZhO17_bomb)	C++14	41 / 100	1000 ms	57168 KiB

bomb

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=2505;
char arr[N][N];
int zero[N][N],n,m,vis[N][N];
int get(int x,int y,int xx,int yy){
	return zero[xx][yy]-zero[xx][y-1]-zero[x-1][yy]+zero[x-1][y-1];
}
bool ok(int x,int y){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			vis[i][j]=0;
	for(int i=1;i+x-1<=n;i++)
		for(int j=1;j+y-1<=m;j++)
			if(!get(i,j,i+x-1,j+y-1)){
				vis[i+x-1][j+y-1]++;
				vis[i-1][j-1]++;
				vis[i+x-1][j-1]--;
				vis[i-1][j+y-1]--;
			}
	for(int i=n;i>=1;i--)
		for(int j=m;j>=1;j--){
			vis[i][j]+=vis[i+1][j]+vis[i][j+1]-vis[i+1][j+1];
			if(!vis[i][j] and arr[i][j]=='1')
				return 0;
		}
	return 1;	
}
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			char c;
			scanf(" %c",&c);
			if(c=='0')
				zero[i][j]++;
			zero[i][j]+=zero[i-1][j]+zero[i][j-1]-zero[i-1][j-1];	
			arr[i][j]=c;
		}
	if(get(1,1,n,m)==n*m){
		puts("0");
		return 0;
	}		
	int p=0;		
	for(int i=m;i>=1;i--)		
		if(ok(1,i)){
			p=i;
			break;
		}
	int ans=p;	
	for(int i=2;i<=n;i++){
		while(p>=1 and !ok(i,p))
			p--;
		if(p>=1 and ok(i,p))
			umax(ans,i*p);
	}	
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
bomb.cpp:52:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&c);
                   ^

• Subtask 1: 41 / 100