Submission #884609

#	Time	Username	Problem	Language	Result	Execution time	Memory
884609		tsumondai	Bomb (IZhO17_bomb)	C++14	100 / 100	98 ms	80148 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2500+ 5;

const int oo = 1e9, mod = 1e9 + 7;

int a[N][N], u[N][N], d[N][N], ans[N];

void process() {
	int mnr = oo, mnc = oo;
	int n, m;
	cin >> n >> m;
	foru(i,1,n) {
		foru(j,1,m) {
			char c;
			cin >> c;
			a[i][j] = c - '0';
		}
	}

	foru(i,1,n) {
		foru(j,1,m) {
			if (a[i][j]) u[i][j] = u[i - 1][j] + 1;
		}
	}

	for (int i = n; i > 0; i--) {
		foru(j,1,m) {
			if (a[i][j]) {
				d[i][j] = d[i + 1][j] + 1;
				if (a[i + 1][j] == 0) mnc = min(mnc, u[i][j]);
			}
		}
	}


	foru(i,1,m) ans[i] = mnc;

	foru(i,1,n) {
		int aa = oo, b = oo, c = 0;
		foru(j,1,m) {
			if (a[i][j] == 0) {
				if (c != 0) mnc = min(c, mnc);
				aa = b = oo, c = 0;
			} else {
				aa = min(aa, d[i][j]);
				b = min(b, u[i][j]);
				c++;
				ans[c] = min(ans[c], b + aa - 1);
			}
		}

		aa = oo, b = oo, c = 0;
		ford(j,m,0) {
			if (a[i][j] == 0) {
				if (c != 0) mnr = min(mnr, c);
				aa = b = oo, c = 0;
			} else {
				aa = min(d[i][j], aa);
				b = min(u[i][j], b);
				c++;
				ans[c] = min(ans[c], b + aa - 1);
			}
		}
		if (c > 0) mnr = min(mnr, c);
	}
	int mx = 0;
	foru(i,1,mnr) {
		mx = max(ans[i] * i, mx);
	}
	cout << mx << "\n";
	return;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

• Subtask 1: 100 / 100