제출 #1126967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126967		bekzhan29	Bomb (IZhO17_bomb)	C++20	8 / 100	1101 ms	74004 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF (long long)(2e15)
#define mod2 998244353
#define mod 1000000007
#define eps 1e-9
#define abs(x) ((x)>=0?(x):-(x))
#define y1 solai
#define fi first
#define se second
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef pair<pll, ll> plll;
mt19937 rng(29);
const ll N=2505;
ll n,m,a[N][N],h,w,u[N][N],sum[N][N],ans;
string s;
inline ll get(ll x, ll y, ll h, ll w)
{
	return sum[x+h-1][y+w-1]-sum[x-1][y+w-1]-sum[x+h-1][y-1]+sum[x-1][y-1];
}
inline ll f(ll h, ll w)
{
	for(ll i=1;i<=h;i++)
		for(ll j=1;j<=w;j++)
			u[i][j]=0;
	for(ll i=1;i<=n;i++)
	{
		if(i+h<=n)
			for(ll j=1;j<=w;j++)
				u[i+h][j]=0;
		for(ll j=1;j<=m;j++)
		{
			if(j+w<=m&&i+h<=n)
				u[i+h][j+w]=0;
			if(i+h-1<=n&&j+w-1<=m&&get(i,j,h,w)==h*w)
			{
				u[i][j]++;
				u[i+h][j+w]++;
				u[i+h][j]--;
				u[i][j+w]--;
			}
			u[i][j]+=u[i-1][j]+u[i][j-1]-u[i-1][j-1];
			if(a[i][j]&&!u[i][j]) 
				return 0;
		}
	}
	return 1;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin>>n>>m;
	h=n;
	w=m;
	for(ll i=1;i<=n;i++)
	{
		cin>>s;
		for(ll j=1;j<=m;j++)
		{
			a[i][j]=s[j-1]-'0';
			sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	w=m;
	for(h=1;h<=n;h++)
	{
		while(w>ans/h&&!f(h,w))
			w--;
		ans=max(ans,h*w);
	}
	cout<<ans;
}
/*
5 6
001000
111110
111110
111110
000100

*/

• Subtask 1: 8 / 100