Submission #768228

#	Time	Username	Problem	Language	Result	Execution time	Memory
768228		rainboy	Bomb (IZhO17_bomb)	C11	100 / 100	426 ms	110540 KiB

bomb

#include <stdio.h>

#define N	2500
#define M	2500

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	static char cc[N][M + 1];
	static int ll[N][M], rr[N][M], uu[N][M], dd[N][M], yy[N + 1];
	int n, m, i, i_, j, j_, l, r, u, d, x, y, ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++)
			ll[i][j] = cc[i][j] == '0' ? j + 1 : (j == 0 ? 0 : ll[i][j - 1]);
		for (j = m - 1; j >= 0; j--)
			rr[i][j] = cc[i][j] == '0' ? j - 1 : (j + 1 == m ? m - 1 : rr[i][j + 1]);
	}
	for (j = 0; j < m; j++) {
		for (i = 0; i < n; i++)
			uu[i][j] = cc[i][j] == '0' ? i + 1 : (i == 0 ? 0 : uu[i - 1][j]);
		for (i = n - 1; i >= 0; i--)
			dd[i][j] = cc[i][j] == '0' ? i - 1 : (i + 1 == n ? n - 1 : dd[i + 1][j]);
	}
	for (x = 1; x <= n; x++)
		yy[x] = m;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			if (ll[i][j] == j) {
				j_ = j, u = 0, d = n - 1;
				while (j_ <= rr[i][j]) {
					u = max(u, uu[i][j_]), d = min(d, dd[i][j_]);
					x = d - u + 1, y = j_ - j;
					if (x < n)
						yy[x + 1] = min(yy[x + 1], y);
					j_++;
				}
				x = 0, y = j_ - j;
				if (x < n)
					yy[x + 1] = min(yy[x + 1], y);
			}
			if (rr[i][j] == j) {
				j_ = j, u = 0, d = n - 1;
				while (j_ >= ll[i][j]) {
					u = max(u, uu[i][j_]), d = min(d, dd[i][j_]);
					x = d - u + 1, y = j - j_;
					if (x < n)
						yy[x + 1] = min(yy[x + 1], y);
					j_--;
				}
				x = 0, y = j - j_;
				if (x < n)
					yy[x + 1] = min(yy[x + 1], y);
			}
			if (uu[i][j] == i) {
				i_ = i, l = 0, r = m - 1;
				while (i_ <= dd[i][j]) {
					l = max(l, ll[i_][j]), r = max(r, rr[i_][j]);
					x = i_ - i, y = r - l + 1;
					if (x < n)
						yy[x + 1] = min(yy[x + 1], y);
					i_++;
				}
				x = i_ - i, y = 0;
				if (x < n)
					yy[x + 1] = min(yy[x + 1], y);
			}
			if (dd[i][j] == i) {
				i_ = i, l = 0, r = m - 1;
				while (i_ >= uu[i][j]) {
					l = max(l, ll[i_][j]), r = max(r, rr[i_][j]);
					x = i - i_, y = r - l + 1;
					if (x < n)
						yy[x + 1] = min(yy[x + 1], y);
					i_--;
				}
				x = i - i_, y = 0;
				if (x < n)
					yy[x + 1] = min(yy[x + 1], y);
			}
		}
	y = m, ans = 0;
	for (x = 1; x <= n; x++) {
		y = min(y, yy[x]);
		ans = max(ans, x * y);
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

bomb.c: In function 'main':
bomb.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bomb.c:16:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100