제출 #1126976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126976		bekzhan29	Bomb (IZhO17_bomb)	C++20	9 / 100	1100 ms	73996 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 check(ll h, ll w)
{
	for(ll i=1;i<=h;i++)
		for(ll j=1;j<=m;j++)
			u[i][j]=0;
	ll n2=n-h+1,m2=m-w+1;
	for(ll i=1;i<=n2;i++)
	{
		for(ll j=1;j<=w;j++)
			u[i+h][j]=0;
		for(ll j=1;j<=m2;j++)
		{
			u[i+h][j+w]=0;
			if(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;
		}
	}
	for(ll i=1;i<=n;i++)
		for(ll j=(i<=n2?m2+1:1);j<=m;j++)
		{
			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;
}
ll f(ll h)
{
	ll l=0,r=m,mid;
	while(l<r)
	{
		mid=(l+r+1)/2;
		if(check(h,mid))
			l=mid;
		else
			r=mid-1;
	}
	return h*l;
}
void solve()
{
	ll l=0,r=n,m1,m2;
	while(l<r)
	{
		m1=l+(r-l)/3;
		m2=r-(r-l)/3;
		if(f(m1)>f(m2))
			r=m2-1;
		else
			l=m1+1;
	}
	ans=f(l);
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin>>n>>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];
		}
	}
	solve();
	cout<<ans;
}
/*
5 6
001000
111110
111110
111110
000100

*/

• Subtask 1: 9 / 100