Submission #709896

#	Time	Username	Problem	Language	Result	Execution time	Memory
709896		rainboy	Sandcastle 2 (JOI22_ho_t5)	C11	100 / 100	1100 ms	18580 KiB

Main

#include <stdio.h>
#include <string.h>

#define NM	50000

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

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

int aa[NM], bb[NM], dd[NM], bad[3][3][3][3][NM], cc[3][3][NM], n, m;

int count(int il, int ir, int j, int y, int z) {
	int i, w, x, cnt;

	if (ir - il < 3) {
		cnt = 0;
		for (i = il; i <= ir; i++) {
			w = min(i - il, 2), x = min(ir - i, 2);
			if (bad[w][x][y][z][i * m + j])
				cnt++;
		}
	} else {
		cnt = 0;
		for (i = il; i < il + 2; i++)
			if (bad[i - il][2][y][z][i * m + j])
				cnt++;
		for (i = ir - 1; i <= ir; i++)
			if (bad[2][ir - i][y][z][i * m + j])
				cnt++;
		cnt += cc[y][z][(ir - 2) * m + j] - cc[y][z][(il + 1) * m + j];
	}
	return cnt;
}

int main() {
	static int dp[3][3][2], dq[3][3][2];
	int h, h_, i, j, i_, j_, i1, j1, il, jl, ir, jr, ij, ij_, ij1, k, w, x, y, y_, z, z_, c, c_, tmp, ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &aa[i * m + j]);
	if (n > m) {
		for (ij = 0; ij < n * m; ij++) {
			i = ij / m, j = ij % m;
			bb[j * n + i] = aa[i * m + j];
		}
		tmp = n, n = m, m = tmp;
		memcpy(aa, bb, n * m * sizeof *bb);
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			ij = i * m + j;
			for (w = 0; w < 3 && (il = i - w) >= 0; w++)
				for (x = 0; x < 3 && (ir = i + x) < n; x++)
					for (y = 0; y < 3 && (jl = j - y) >= 0; y++)
						for (z = 0; z < 3 && (jr = j + z) < m; z++) {
							k = 0;
							for (h = 0; h < 4; h++) {
								i_ = i + di[h], j_ = j + dj[h], ij_ = i_ * m + j_;
								if (i_ >= il && i_ <= ir && j_ >= jl && j_ <= jr && aa[ij_] > aa[ij]) {
									k++;
									for (h_ = 0; h_ < 4; h_++) {
										i1 = i_ + di[h_], j1 = j_ + dj[h_], ij1 = i1 * m + j1;
										if (i1 >= il && i1 <= ir && j1 >= jl && j1 <= jr && aa[ij_] > aa[ij1] && aa[ij1] > aa[ij]) {
											k--;
											break;
										}
									}
								}
							}
							if (k != 1) {
								bad[w][x][y][z][ij] = 1;
								if (w == 2 && x == 2)
									cc[y][z][ij] = 1;
							}
						}
		}
	for (y = 0; y < 3; y++)
		for (z = 0; z < 3; z++)
			for (ij = m; ij < n * m; ij++)
				cc[y][z][ij] += cc[y][z][ij - m];
	ans = 0;
	for (il = 0; il < n; il++)
		for (ir = il; ir < n; ir++) {
			memset(dp, 0, sizeof dp);
			for (j = 0; j < m; j++) {
				memset(dq, 0, sizeof dq);
				c = count(il, ir, j, 0, 0);
				if (c < 2)
					dq[0][0][c]++;
				c = count(il, ir, j, 0, 1);
				if (c < 2)
					dq[0][1][c]++;
				c = count(il, ir, j, 0, 2);
				if (c < 2)
					dq[0][2][c]++;
				for (y = 0; y < 3; y++)
					for (z = 0; z < 3; z++)
						for (c = 0; c < 2; c++) {
							int v = dp[y][z][c];

							if (v == 0)
								continue;
							if (z > 0) {
								y_ = min(y + 1, 2), z_ = z - 1, c_ = c + count(il, ir, j, y_, z_);
								if (c_ < 2)
									dq[y_][z_][c_] += v;
							}
							if (z == 2) {
								y_ = min(y + 1, 2), z_ = z, c_ = c + count(il, ir, j, y_, z_);
								if (c_ < 2)
									dq[y_][z_][c_] += v;
							}
						}
				memcpy(dp, dq, sizeof dq);
				ans += dp[0][0][1] + dp[1][0][1] + dp[2][0][1];
			}
		}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:40:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:43:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |    scanf("%d", &aa[i * m + j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 20 / 20