Submission #167417

#	Time	Username	Problem	Language	Result	Execution time	Memory
167417		GioChkhaidze	Bomb (IZhO17_bomb)	C++14	44 / 100	644 ms	42360 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];
bool f[N][N];
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++)
			if (s[i][j]=='1') f[i][j]=1;
					     else f[i][j]=0;
						 								     
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++) 
			if (s[i][j]=='1')
				if (i+x-1<n && j+y-1<m) {
					if (D[i+x][j+y]-D[i][j+y]-D[i+x][j]+D[i][j]!=0 && !f[i][j]) continue;
					if (D[i+x][j+y]-D[i][j+y]-D[i+x][j]+D[i][j]!=0) return 0;
					for (int k1=i; k1<i+x; k1++)
						for (int k2=j; k2<j+y; k2++)
							f[k1][k2]=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*n*m*length*width>=3e8) {
 		cout<<length*width<<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:33:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bomb.cpp: In function 'int main()':
bomb.cpp:34: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: 44 / 100