Submission #43065

#	Time	Username	Problem	Language	Result	Execution time	Memory
43065		cheater2k	Bomb (IZhO17_bomb)	C++14	23 / 100	1016 ms	131072 KiB

bomb

#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' && !vis[i][j]) {
			vis[i][j] = 1;
			queue < pair<int,int> > q;
			q.push({i, j});

			while(!q.empty()) {
				int x = q.front().first, y = q.front().second; q.pop();
				nrow = min(nrow, up[x][y] + down[x][y] - 1);
				ncol = min(ncol, left[x][y] + right[x][y] - 1);
				for (int dir = 0; dir < 4; ++dir) {
					int nx = x + dx[dir];
					int ny = y + dy[dir];
					if (nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '0' || vis[nx][ny]) continue;
					vis[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}

	printf("%d\n", nrow * ncol);
}

• Subtask 1: 23 / 100