oj.uz

Submission #785027

# Submission time Handle Problem Language Result Execution time Memory
785027 2023-07-17T00:21:56 Z rainboy Game (eJOI20_game) C
100 / 100
 1 ms 724 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 292 KB Output is correct
16 Correct 0 ms 212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 296 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 264 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 292 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 296 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 296 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 292 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 296 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 296 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 1 ms 264 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 300 KB Output is correct
53 Correct 0 ms 340 KB Output is correct
54 Correct 0 ms 292 KB Output is correct
55 Correct 0 ms 340 KB Output is correct
56 Correct 0 ms 340 KB Output is correct
57 Correct 0 ms 340 KB Output is correct
58 Correct 0 ms 340 KB Output is correct
59 Correct 0 ms 340 KB Output is correct
60 Correct 0 ms 340 KB Output is correct
61 Correct 0 ms 340 KB Output is correct
62 Correct 0 ms 292 KB Output is correct
63 Correct 0 ms 340 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 0 ms 340 KB Output is correct
66 Correct 1 ms 596 KB Output is correct
67 Correct 1 ms 596 KB Output is correct
68 Correct 1 ms 596 KB Output is correct
69 Correct 1 ms 596 KB Output is correct
70 Correct 1 ms 680 KB Output is correct
71 Correct 1 ms 596 KB Output is correct
72 Correct 1 ms 680 KB Output is correct
73 Correct 0 ms 468 KB Output is correct
74 Correct 1 ms 596 KB Output is correct
75 Correct 1 ms 676 KB Output is correct
76 Correct 1 ms 596 KB Output is correct
77 Correct 1 ms 724 KB Output is correct
78 Correct 1 ms 596 KB Output is correct
79 Correct 0 ms 596 KB Output is correct
80 Correct 1 ms 724 KB Output is correct
81 Correct 1 ms 596 KB Output is correct
82 Correct 0 ms 596 KB Output is correct
83 Correct 1 ms 596 KB Output is correct