Submission #917917

#	Time	Username	Problem	Language	Result	Execution time	Memory
917917		SeDunion	Bomb (IZhO17_bomb)	C++17	92 / 100	446 ms	80428 KiB

bomb

#include <iostream>

using namespace std;

const int N = 2505;

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

int L[N][N], R[N][N];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1 ; i <= n ; ++ i) {
		for (int j = 1 ; j <= m ; ++ j) {
			char c;
			cin >> c;
			a[i][j] = (c - '0');
		}
	}
	for (int i = 1 ; i <= n ; ++ i) {
		ans[i] = m;
	}
	int lim = n;
	for (int rep = 0 ; rep < 2 ; ++ rep) {
		for (int i = 1 ; i <= n ; ++ i) {
			for (int j = 1 ; j <= m ; ++ j) {
				if (a[i][j]) L[i][j] = L[i][j - 1] + 1;
				else L[i][j] = 0;
			}
			for (int j = m ; j >= 1 ; -- j) {
				if (a[i][j]) R[i][j] = R[i][j + 1] + 1;
				else R[i][j] = 0;
			}
		}
		for (int j = 1 ; j <= m ; ++ j) {
			int cnt = 0;
			int LX = -1, RX = -1;
			for (int i = 1 ; i <= n + 1 ; ++ i) {
					if (a[i][j]) {
					cnt++;
					if (cnt == 1) {
						LX = L[i][j], RX = R[i][j];
					}
					LX = min(LX, L[i][j]), RX = min(RX, R[i][j]);
					ans[cnt] = min(ans[cnt], LX + RX - 1);
				} else {
					if (cnt > 0) lim = min(lim, cnt);
					LX = RX = -1;
					cnt = 0;
				}
			}
		}
		for (int i = 1 ; i <= n / 2 ; ++ i) {
			for (int j = 1 ; j <= m ; ++ j) {
				swap(a[i][j], a[n - i + 1][j]);
			}
		}
	}
	int	res = 0;
	for (int i = 1 ; i <= lim ; ++ i) {
		//cerr << i << " " << ans[i] << endl;
		ans[i + 1] = min(ans[i + 1], ans[i]);
		res = max(res, ans[i] * i);
	}
	cout << res;
}

• Subtask 1: 92 / 100