Submission #167416

#	Time	Username	Problem	Language	Result	Execution time	Memory
167416		GioChkhaidze	Bomb (IZhO17_bomb)	C++14	41 / 100	570 ms	121668 KiB

bomb

#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left 2*h,l,(l+r)/2
#define Right 2*h+1,(l+r)/2+1,r
#define F first
#define S second
using namespace std;
const int N=2505;
int n,m,width=1e9,length=1e9,last,D[N][N],Dr[N][N],X,Y;
string s[N],S;
vector < pair < int , pair < int , int > > > v;
inline bool check(int x,int y) {
	for (int i=0; i<=n; i++)
		for (int j=0; j<=m; j++)
			Dr[i][j]=0;
	
	for (int i=0; i<n; i++) 
		for (int j=0; j<m; j++)
				if (D[i+x][j+y]-D[i][j+y]-D[i+x][j]+D[i][j]==0 && s[i][j]=='1') 
				   Dr[i+1][j+1]=Dr[i][j+1]+Dr[i+1][j]-Dr[i][j]+1;
					else
				   Dr[i+1][j+1]=Dr[i][j+1]+Dr[i+1][j]-Dr[i][j];
	
					 								     
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++) 
			if (s[i-1][j-1]=='1') {
				X=max(i-x,0),Y=max(j-y,0);
				if (Dr[i][j]-Dr[i][Y]-Dr[X][j]+Dr[X][Y]==0) return 0;
			}
	
	return 1;
}

main () {
	scanf("%d%d",&n,&m);
	getline(cin,S);
	for (int i=0; i<n; i++)  
		getline(cin,s[i]);
	
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++) 
			D[i+1][j+1]=D[i][j+1]+D[i+1][j]-D[i][j]+(s[i][j]=='0');
	
	for (int i=0; i<n; i++) {
		last=m;
		for (int j=m-1; j>=0; j--) {
			if (s[i][j]=='0' && last-1!=j) 
				if (width>last-j-1) width=last-j-1;
			if (s[i][j]=='0') last=j;
		}
		
		if (last) 
			if (last<width) width=last;
	}
	
	for (int j=0; j<m; j++) {
		last=n;
		for (int i=n-1; i>=0; i--) {
			if (s[i][j]=='0' && last-1!=i) 
				if (length>last-i-1) length=last-i-1;
			if (s[i][j]=='0') last=i;
		}
		
		if (last)
			if (last<length) length=last;
	}
	
	if (width==1e9 || length==1e9) { cout<<0<<endl; return 0; }

	if (1LL*width*length*n*m>=3e8) {
		cout<<width*length<<endl;
		return 0;
	}

	for (int i=1; i<=length; i++)
		for (int j=1; j<=width; j++)
			v.push_back({i*j,{i,j}});
			
	sort(v.begin(),v.end());
	
	for (int i=v.size()-1; i>=0; i--) {
		if (check(v[i].S.F,v[i].S.S)) {
			cout<<v[i].F<<endl;
			return 0;
		}
	}
}

Compilation message (stderr)

bomb.cpp:35:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bomb.cpp: In function 'int main()':
bomb.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 41 / 100