제출 #1258391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258391		TAhmed33	Bomb (IZhO17_bomb)	C++20	17 / 100	1102 ms	80380 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
0011
0011
1110
1100
*/
void solve (int X) {
	int n, m; cin >> n >> m;
	vector <vector <char>> a(n + 1, vector <char> (m + 1));
	vector <vector <int>> up(n + 1, vector <int> (m + 1, 0));
	vector <vector <int>> down(n + 2, vector <int> (m + 1, 0));
	vector <vector <int>> f(n + 2, vector <int> (m + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			up[i][j] = (a[i][j] == '0' ? 0 : 1 + up[i - 1][j]);
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= m; j++) {
			down[i][j] = (a[i][j] == '0' ? 0 : 1 + down[i + 1][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			f[i][j] = up[i][j] + down[i][j] - 1;
		}
	}
	int dx = n, dy = m;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '1') {
				cnt++;
			} else if (cnt > 0) {
				dy = min(dy, cnt);
				cnt = 0;
			}
		}
		if (cnt > 0) {
			dy = min(dy, cnt);
			cnt = 0;
		}
	}
	for (int j = 1; j <= m; j++) {
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i][j] == '1') {
				cnt++;
			} else if (cnt > 0) {
				dx = min(dx, cnt);
				cnt = 0;
			}
		}
		if (cnt > 0) {
			dx = min(dx, cnt);
			cnt = 0;
		}
	}
	vector <int> ee(dx + 1, dy);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '0') {
				continue;
			}
			int cur = f[i][j];
			cur = min(cur, dx);
			int l = j, r = j;
			while (l - 1 >= 1 && f[i][l - 1] >= cur) {
				l--;
			}
			while (r + 1 <= m && f[i][r + 1] >= cur) {
				r++;
			}
			ee[cur] = min(ee[cur], r - l + 1);
		}
	}
	int mx = 0;
	for (int i = 1; i <= dx; i++) {
		mx = max(mx, i * ee[i]);
	}
	cout << mx << '\n';
}	
signed main () {
	#ifndef ONLINE_JUDGE 
		//freopen("input_file", "r", stdin);
		//freopen("output_file", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	for (int i = 1; i <= tc; i++) solve(i);
}

• Subtask 1: 17 / 100