Submission #1017486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017486		Gray	Bomb (IZhO17_bomb)	C++17	100 / 100	264 ms	80468 KiB

bomb

#include <cassert>
#include <iostream>
#include <vector>
#define ll int
#define ln "\n"
#define ff first
#define ss second
#define ld long double
const ll INF = 1e9;
const ll MOD = 1e9+7;
using namespace std;

void solve(){
	ll n, m; cin >> n >> m;
	vector<vector<ll>> a(n+1, vector<ll>(m+1)), left(n+1, vector<ll>(m+2)), right(n+1, vector<ll>(m+2));
	for (ll i=1; i<=n; i++) 
		for (ll j=1; j<=m; j++){
			char x; cin >> x;
			a[i][j]=x-'0';
		}
	vector<ll> mxwid(n+1, m);
	for (ll i=1; i<=n; i++) {
		for (ll j=1; j<=m; j++){
			left[i][j] = a[i][j]?left[i][j-1]+1:0;
		}
		for (ll j=m; j>=1; j--){
			right[i][j] = a[i][j]?right[i][j+1]+1:0;
			if (a[i][j])mxwid[1]=min(mxwid[1], right[i][j]+left[i][j]-1);
		}
	}
	ll mxh=n;
	for (ll j=1; j<=m; j++){
		ll l=m, r=m, cc=0;
		for (ll i=1; i<=n; i++){
			if (a[i][j]){
				l=min(l, left[i][j]);
				r=min(r, right[i][j]);
				cc++;
				mxwid[cc]=min(mxwid[cc], l+r-1);
			}else{
				if (cc)mxh=min(mxh, cc);
				cc=0;
				l=m; r=m;
			}
		}
		if (cc) mxh=min(mxh, cc);
	}
	for (ll j=1; j<=m; j++){
		ll l=m, r=m, cc=0;
		for (ll i=n; i>=1; i--){
			if (a[i][j]){
				l=min(l, left[i][j]);
				r=min(r, right[i][j]);
				cc++;
				mxwid[cc]=min(mxwid[cc], l+r-1);
			}else{
				if (cc) mxh=min(mxh, cc);
				cc=0;
				l=m; r=m;
			}
		}
		if (cc) mxh=min(mxh, cc);
	}
	ll ans=0;
	for (ll i=1; i<=mxh; i++){
		// cout << i << ":" << mxwid[i] << ln;
		mxwid[i]=min(mxwid[i-1], mxwid[i]);
		ans=max(ans, mxwid[i]*i);
	}
	cout << ans << ln;
}
void setIO(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}
int main(){
	setIO();
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

• Subtask 1: 100 / 100