Submission #1126949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126949		bekzhan29	Bomb (IZhO17_bomb)	C++20	24 / 100	183 ms	91540 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=3100;
ll n,m,a[N][N],h,w,u[N][N],sum[N][N];
string s;
ll get(ll x, ll y)
{
	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];
}
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];
		}
	}
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++)
		{
			if(!a[i][j])
				continue;
			if(a[i][j+1]==0)
			{
				ll len=0;
				for(ll k=j;k>=1&&a[i][k];k--)
					len++;
				w=min(w,len);
			}
			if(a[i+1][j]==0)
			{
				ll len=0;
				for(ll k=i;k>=1&&a[k][j];k--)
					len++;
				h=min(h,len);
			}
		}
	for(ll i=1;i<=n-h+1;i++)
		for(ll j=1;j<=m-w+1;j++)
			if(get(i,j)==h*w)
			{
				u[i][j]++;
				u[i+h][j+w]++;
				u[i+h][j]--;
				u[i][j+w]--;
			}
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++)
			u[i][j]+=u[i-1][j]+u[i][j-1]-u[i-1][j-1];
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++)
			if(!u[i][j]&&a[i][j])
				assert(0);
	cout<<h*w;
}
/*
*/

• Subtask 1: 24 / 100