Submission #785027

#	Time	Username	Problem	Language	Result	Execution time	Memory
785027		rainboy	Game (eJOI20_game)	C11	100 / 100	1 ms	724 KiB

game

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

#define N	20
#define M	20
#define N_	((N + 1) * M + N * (M + 1))
#define INF	0x3f3f3f3f

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

int ds[N_], sz[N_]; char cycle[N_];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j) {
		cycle[i] = 1;
		return;
	}
	if (ds[i] > ds[j])
		ds[i] = j, sz[j] += sz[i], cycle[j] |= cycle[i];
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, sz[i] += sz[j], cycle[i] |= cycle[j];
	}
}

int main() {
	static char aa[N + 1][M + 1], bb[N][M + 2];
	static int nnp[N * M + 2], nnc[N * M + 2], pp[N + M], cc[N * M], dp[N + M + 1][N + M + 1][N * M + 1];
	int n, ns, ns2, ns3, np, nc, m, n_, i, j, ks, kp, kc, l, u, v, w, x;

	scanf("%d%d", &n, &m), n_ = (n + 1) * m + n * (m + 1);
	for (i = 0; i <= n; i++)
		scanf("%s", aa[i]);
	for (i = 0; i < n; i++)
		scanf("%s", bb[i]);
	memset(ds, -1, n_ * sizeof *ds);
	for (i = 0; i < n_; i++)
		sz[i] = 1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			u = v = -1;
			if (aa[i][j] == '0') {
				w = i * m + j;
				if (u == -1)
					u = w;
				else
					v = w;
			}
			if (aa[i + 1][j] == '0') {
				w = (i + 1) * m + j;
				if (u == -1)
					u = w;
				else
					v = w;
			}
			if (bb[i][j] == '0') {
				w = (n + 1) * m + i * (m + 1) + j;
				if (u == -1)
					u = w;
				else
					v = w;
			}
			if (bb[i][j + 1] == '0') {
				w = (n + 1) * m + i * (m + 1) + (j + 1);
				if (u == -1)
					u = w;
				else
					v = w;
			}
			if (u != -1 && v != -1)
				join(u, v);
		}
	for (i = 0; i < n_; i++)
		if (ds[i] < 0) {
			if (!cycle[i])
				nnp[sz[i]]++;
			else
				nnc[sz[i]]++;
		}
	ns2 = nnp[2], ns3 = nnp[3], ns = ns2 + ns3;
	np = 0;
	for (l = 4; l <= n * m + 1; l++)
		while (nnp[l]--)
			pp[np++] = l;
	nc = 0;
	for (l = 4; l <= n * m + 1; l++)
		while (nnc[l]--)
			cc[nc++] = l;
	for (ks = ns; ks >= 0; ks--)
		for (kp = np; kp >= 0; kp--)
			for (kc = nc; kc >= 0; kc--) {
				if (ks == ns && kp == np && kc == nc)
					x = 0;
				else {
					x = -INF;
					if (ks < ns)
						x = max(x, -dp[ks + 1][kp][kc] - (ks < ns2 ? 1 : 2));
					if (kp < np)
						x = max(x, min(-dp[ks][kp + 1][kc] - pp[kp] + 1, dp[ks][kp + 1][kc] - pp[kp] + 5));
					if (kc < nc)
						x = max(x, min(-dp[ks][kp][kc + 1] - cc[kc], dp[ks][kp][kc + 1] - cc[kc] + 8));
				}
				dp[ks][kp][kc] = x;
			}
	printf("%d\n", dp[0][0][0]);
	return 0;
}

Compilation message (stderr)

game.c: In function 'main':
game.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d", &n, &m), n_ = (n + 1) * m + n * (m + 1);
      |  ^~~~~~~~~~~~~~~~~~~~~
game.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%s", aa[i]);
      |   ^~~~~~~~~~~~~~~~~~
game.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%s", bb[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20