제출 #43148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43148		cheater2k	Bomb (IZhO17_bomb)	C++14	63 / 100	1088 ms	131072 KiB

bomb

/*
5 5 
00111
00111
11111
11110
11100
*/
#include <bits/stdc++.h>
using namespace std;

#define left __left
#define right __right

const int N = 2505;
const int dx[] = {0, 0, -1, +1};
const int dy[] = {-1, +1, 0, 0};

int n, m, nrow, ncol;
int left[N][N];
int right[N][N];
int up[N][N];
int down[N][N];
char a[N][N];
bool vis[N][N];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	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) left[i][j] = a[i][j] == '1' ? left[i][j - 1] + 1 : 0;
		for (int j = m; j >= 1; --j) right[i][j] = a[i][j] == '1' ? right[i][j + 1] + 1 : 0;
	}

	for (int j = 1; j <= m; ++j) {
		for (int i = 1; i <= n; ++i) up[i][j] = a[i][j] == '1' ? up[i - 1][j] + 1 : 0;
		for (int i = n; i >= 1; --i) down[i][j] = a[i][j] == '1' ? down[i + 1][j] + 1 : 0;
	}

	nrow = n, ncol = m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) if (a[i][j] == '1') {
			nrow = min(nrow, up[i][j] + down[i][j] - 1);
			ncol = min(ncol, left[i][j] + right[i][j] - 1);
		}
	}

	int res = 0;
	for (int r = 1; r <= nrow; ++r) {
		int c = ncol;
		for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
			if (a[i][j] != '1') continue;

			if (down[i][j] == 1) {
				for (int k = i; k >= i - r + 1; --k) {
					if (left[i][j] == 1) c = min(c, right[k][j]);
					if (right[i][j] == 1) c = min(c, left[k][j]);
				}
			} else if (up[i][j] == 1) {
				for (int k = i; k <= i + r - 1; ++k) {
					if (left[i][j] == 1) c = min(c, right[k][j]);
					if (right[i][j] == 1) c = min(c, left[k][j]);
				}
			}
		}

		res = max(res, r * c);
	}

	cout << res << endl;
}

• Subtask 1: 63 / 100