Submission #709894

#	Time	Username	Problem	Language	Result	Execution time	Memory
709894		rainboy	Sandcastle 2 (JOI22_ho_t5)	C11	71 / 100	5071 ms	3276 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, i, j, i_, j_, il, jl, ir, jr, ij, ij_, ij1, 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 (il = 0; il < n; il++)
		for (ir = il; ir < n && ir < il + 5; ir++)
			for (jl = 0; jl < m; jl++)
				for (jr = 0; jr < m && jr < jl + 5; jr++) {
					for (i = il; i <= ir; i++)
						for (j = jl; j <= jr; j++)
							dd[i * m + j] = 0;
					for (i = il; i <= ir; i++)
						for (j = jl; j <= jr; j++) {
							ij = i * m + j, ij1 = -1;
							for (h = 0; h < 4; h++) {
								i_ = i + di[h], j_ = j + dj[h];
								if (i_ >= il && i_ <= ir && j_ >= jl && j_ <= jr) {
									ij_ = i_ * m + j_;
									if (aa[ij_] < aa[ij] && (ij1 == -1 || aa[ij1] < aa[ij_]))
										ij1 = ij_;
								}
							}
							if (ij1 != -1)
								dd[ij1]++;
						}
					for (i = il; i <= ir; i++)
						for (j = jl; j <= jr; j++) {
							ij = i * m + j;
							if (dd[ij] != 1) {
								w = min(i - il, 2), x = min(ir - i, 2), y = min(j - jl, 2), z = min(jr - j, 2);
								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: 0 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 0 / 20