Submission #88091

#	Time	Username	Problem	Language	Result	Execution time	Memory
88091		Pajaraja	Bomb (IZhO17_bomb)	C++17	4 / 100	1094 ms	132096 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
bool t[2507][2507],r[2507][2507];
int p[2507][2507],d[2507][2507],n,m;
bool provera(int x,int y)
{
	for(int i=x;i<=n;i++) for(int j=y;j<=m;j++) r[i][j]=(p[i][j]-p[i-x][j]-p[i][j-y]+p[i-x][j-y]==x*y);
	for(int i=n;i>0;i--) for(int j=m;j>0;j--) d[i][j]=r[i][j]+d[i+1][j]+d[i][j+1]-d[i+1][j+1];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(t[i][j] && p[i][j]-p[i+x][j]-p[i][j+y]+p[i+x][j+y]==0) return false;
	return true;
}
int main()
{
	int lh=2507,lv=2507;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		for(int j=1;j<=m;j++) t[i][j]=(s[j-1]=='1'?1:0);
	}
	for(int i=1;i<=n;i++)
	{
		int cur=0;
		for(int j=1;j<=m;j++)
		{
			if(t[i][j]==0) {if(cur!=0) lh=min(lh,cur); cur=0;}
			else cur++;
		}
		if(cur!=0) lh=min(lh,cur);
	}
	for(int i=1;i<=m;i++)
	{
		int cur=0;
		for(int j=1;j<=n;j++)
		{
			if(t[j][i]==0) { if(cur!=0) lv=min(lv,cur); cur=0;}
			else cur++;
		}
		if(cur!=0) lv=min(lv,cur);
	}
	int sol=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) p[i][j]=t[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
	for(int i=1;i<=lv;i++)
	{
		while(!provera(i,lv)) lh--; 
		sol=max(sol,lh*i);
	}
	printf("%d",sol);
}

• Subtask 1: 4 / 100