Submission #1127672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127672		Tsagana	Bomb (IZhO17_bomb)	C++20	42 / 100	542 ms	147332 KiB

bomb

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int a[2501][2501];
int L[2501][2501];
int R[2501][2501];
int ans[2501];

void solve () {
	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++) {
		memset(L, 0, sizeof L);
		memset(R, 0, sizeof R);

		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;
			for (int j = m; j >= 1; j--) if (a[i][j]) R[i][j] = R[i][j + 1] + 1;
			for (int j = 1; j <= m; j++) if (a[i][j]) ans[1] = min(ans[1], L[i][j] + R[i][j] - 1);
		}

		for (int j = 1; j <= m; j++) {
			int cnt = 0, 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++) {
		ans[i+1] = min(ans[i+1], ans[i]);
		res = max(res, ans[i]*i);
	}
	cout << res;
}
signed main() {IOS solve(); return 0;}

• Subtask 1: 42 / 100