답안 #500619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500619	2021-12-31T15:18:10 Z	rainboy	Tortoise (CEOI21_tortoise)	C	8 / 100	403 ms	332900 KB

tortoise

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

#define N	20
#define INF	0x3f3f3f3f

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

int main() {
	static int aa[N], dp[1 << N][N][2], dq[1 << N][N][2];
	int n, i, b, t, s, s_, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (b = 0; b < 1 << n; b++)
		for (i = 0; i < n; i++)
			dp[b][i][0] = dp[b][i][1] = INF;
	dp[0][0][0] = 0;
	for (t = 0; t <= (n - 1) * 2; t++) {
		s = 1 << (t + 1) / 2, s_ = 1 << (t + 2) / 2;
		for (b = 0; b < 1 << n; b += s)
			for (i = 0; i < n; i++)
				dq[b][i][0] = dq[b][i][1] = INF;
		for (b = 0; b < 1 << n; b += s)
			for (i = 0; i < n; i++) {
				if ((b & 1 << i) == 0 && aa[i] == 1)
					dp[b | 1 << i][i][1] = min(dp[b | 1 << i][i][1], dp[b][i][0]);
				if (aa[i] == -1)
					dp[b][i][0] = min(dp[b][i][0], dp[b][i][1]);
			}
		for (b = 0; b < 1 << n; b += s)
			for (i = 0; i < n; i++) {
				dq[b][i][0] = min(dq[b][i][0], dp[b][i][0]);
				dq[b][i][1] = min(dq[b][i][1], dp[b][i][1]);
				if (i > 0) {
					dq[b][i - 1][0] = min(dq[b][i - 1][0], dp[b][i][0]);
					dq[b][i - 1][1] = min(dq[b][i - 1][1], dp[b][i][1]);
				}
				if (i + 1 < n) {
					dq[b][i + 1][0] = min(dq[b][i + 1][0], dp[b][i][0]);
					dq[b][i + 1][1] = min(dq[b][i + 1][1], dp[b][i][1]);
				}
			}
		if (t % 2 == 0)
			for (b = 0; b < 1 << n; b += s_)
				for (i = 0; i < n; i++) {
					if (aa[t / 2] == 1)
						dq[b][i][0]++, dq[b][i][1]++;
					dq[b][i][0] = min(dq[b][i][0], dq[b | 1 << t / 2][i][0]);
					dq[b][i][1] = min(dq[b][i][1], dq[b | 1 << t / 2][i][1]);
				}
		for (b = 0; b < 1 << n; b += s_)
			for (i = 0; i < n; i++)
				dp[b][i][0] = dq[b][i][0], dp[b][i][1] = dq[b][i][1];
		for (b = 0; b < 1 << n; b += s_)
			for (i = 0; i < n; i++) {
				if ((b & 1 << i) == 0 && aa[i] == 1)
					dp[b | 1 << i][i][1] = min(dp[b | 1 << i][i][1], dp[b][i][0]);
				if (aa[i] == -1)
					dp[b][i][0] = min(dp[b][i][0], dp[b][i][1]);
			}
	}
	ans = INF;
	for (i = 0; i < n; i++)
		ans = min(ans, min(dp[0][i][0], dp[0][i][1]));
	printf("%d\n", ans);
	return 0;
}

Compilation message

tortoise.c: In function 'main':
tortoise.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
tortoise.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	20884 KB	Output is correct
2	Correct	92 ms	20684 KB	Output is correct
3	Correct	72 ms	20792 KB	Output is correct
4	Correct	76 ms	20676 KB	Output is correct
5	Correct	67 ms	20792 KB	Output is correct
6	Correct	127 ms	20732 KB	Output is correct
7	Correct	76 ms	20804 KB	Output is correct
8	Correct	75 ms	20684 KB	Output is correct
9	Correct	71 ms	20796 KB	Output is correct
10	Correct	68 ms	20760 KB	Output is correct
11	Correct	74 ms	20684 KB	Output is correct
12	Correct	73 ms	20796 KB	Output is correct
13	Correct	72 ms	20792 KB	Output is correct
14	Correct	74 ms	20792 KB	Output is correct
15	Correct	72 ms	20684 KB	Output is correct
16	Correct	87 ms	20788 KB	Output is correct
17	Correct	84 ms	20788 KB	Output is correct
18	Correct	64 ms	20796 KB	Output is correct
19	Correct	77 ms	20812 KB	Output is correct
20	Correct	71 ms	20804 KB	Output is correct
21	Correct	67 ms	20684 KB	Output is correct
22	Correct	69 ms	20792 KB	Output is correct
23	Correct	82 ms	20788 KB	Output is correct
24	Correct	78 ms	20788 KB	Output is correct
25	Correct	68 ms	20764 KB	Output is correct
26	Correct	68 ms	20832 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	20884 KB	Output is correct
2	Correct	92 ms	20684 KB	Output is correct
3	Correct	72 ms	20792 KB	Output is correct
4	Correct	76 ms	20676 KB	Output is correct
5	Correct	67 ms	20792 KB	Output is correct
6	Correct	127 ms	20732 KB	Output is correct
7	Correct	76 ms	20804 KB	Output is correct
8	Correct	75 ms	20684 KB	Output is correct
9	Correct	71 ms	20796 KB	Output is correct
10	Correct	68 ms	20760 KB	Output is correct
11	Correct	74 ms	20684 KB	Output is correct
12	Correct	73 ms	20796 KB	Output is correct
13	Correct	72 ms	20792 KB	Output is correct
14	Correct	74 ms	20792 KB	Output is correct
15	Correct	72 ms	20684 KB	Output is correct
16	Correct	87 ms	20788 KB	Output is correct
17	Correct	84 ms	20788 KB	Output is correct
18	Correct	64 ms	20796 KB	Output is correct
19	Correct	77 ms	20812 KB	Output is correct
20	Correct	71 ms	20804 KB	Output is correct
21	Correct	67 ms	20684 KB	Output is correct
22	Correct	69 ms	20792 KB	Output is correct
23	Correct	82 ms	20788 KB	Output is correct
24	Correct	78 ms	20788 KB	Output is correct
25	Correct	68 ms	20764 KB	Output is correct
26	Correct	68 ms	20832 KB	Output is correct
27	Runtime error	403 ms	332900 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	20884 KB	Output is correct
2	Correct	92 ms	20684 KB	Output is correct
3	Correct	72 ms	20792 KB	Output is correct
4	Correct	76 ms	20676 KB	Output is correct
5	Correct	67 ms	20792 KB	Output is correct
6	Correct	127 ms	20732 KB	Output is correct
7	Correct	76 ms	20804 KB	Output is correct
8	Correct	75 ms	20684 KB	Output is correct
9	Correct	71 ms	20796 KB	Output is correct
10	Correct	68 ms	20760 KB	Output is correct
11	Correct	74 ms	20684 KB	Output is correct
12	Correct	73 ms	20796 KB	Output is correct
13	Correct	72 ms	20792 KB	Output is correct
14	Correct	74 ms	20792 KB	Output is correct
15	Correct	72 ms	20684 KB	Output is correct
16	Correct	87 ms	20788 KB	Output is correct
17	Correct	84 ms	20788 KB	Output is correct
18	Correct	64 ms	20796 KB	Output is correct
19	Correct	77 ms	20812 KB	Output is correct
20	Correct	71 ms	20804 KB	Output is correct
21	Correct	67 ms	20684 KB	Output is correct
22	Correct	69 ms	20792 KB	Output is correct
23	Correct	82 ms	20788 KB	Output is correct
24	Correct	78 ms	20788 KB	Output is correct
25	Correct	68 ms	20764 KB	Output is correct
26	Correct	68 ms	20832 KB	Output is correct
27	Runtime error	403 ms	332900 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	20884 KB	Output is correct
2	Correct	92 ms	20684 KB	Output is correct
3	Correct	72 ms	20792 KB	Output is correct
4	Correct	76 ms	20676 KB	Output is correct
5	Correct	67 ms	20792 KB	Output is correct
6	Correct	127 ms	20732 KB	Output is correct
7	Correct	76 ms	20804 KB	Output is correct
8	Correct	75 ms	20684 KB	Output is correct
9	Correct	71 ms	20796 KB	Output is correct
10	Correct	68 ms	20760 KB	Output is correct
11	Correct	74 ms	20684 KB	Output is correct
12	Correct	73 ms	20796 KB	Output is correct
13	Correct	72 ms	20792 KB	Output is correct
14	Correct	74 ms	20792 KB	Output is correct
15	Correct	72 ms	20684 KB	Output is correct
16	Correct	87 ms	20788 KB	Output is correct
17	Correct	84 ms	20788 KB	Output is correct
18	Correct	64 ms	20796 KB	Output is correct
19	Correct	77 ms	20812 KB	Output is correct
20	Correct	71 ms	20804 KB	Output is correct
21	Correct	67 ms	20684 KB	Output is correct
22	Correct	69 ms	20792 KB	Output is correct
23	Correct	82 ms	20788 KB	Output is correct
24	Correct	78 ms	20788 KB	Output is correct
25	Correct	68 ms	20764 KB	Output is correct
26	Correct	68 ms	20832 KB	Output is correct
27	Runtime error	403 ms	332900 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	20884 KB	Output is correct
2	Correct	92 ms	20684 KB	Output is correct
3	Correct	72 ms	20792 KB	Output is correct
4	Correct	76 ms	20676 KB	Output is correct
5	Correct	67 ms	20792 KB	Output is correct
6	Correct	127 ms	20732 KB	Output is correct
7	Correct	76 ms	20804 KB	Output is correct
8	Correct	75 ms	20684 KB	Output is correct
9	Correct	71 ms	20796 KB	Output is correct
10	Correct	68 ms	20760 KB	Output is correct
11	Correct	74 ms	20684 KB	Output is correct
12	Correct	73 ms	20796 KB	Output is correct
13	Correct	72 ms	20792 KB	Output is correct
14	Correct	74 ms	20792 KB	Output is correct
15	Correct	72 ms	20684 KB	Output is correct
16	Correct	87 ms	20788 KB	Output is correct
17	Correct	84 ms	20788 KB	Output is correct
18	Correct	64 ms	20796 KB	Output is correct
19	Correct	77 ms	20812 KB	Output is correct
20	Correct	71 ms	20804 KB	Output is correct
21	Correct	67 ms	20684 KB	Output is correct
22	Correct	69 ms	20792 KB	Output is correct
23	Correct	82 ms	20788 KB	Output is correct
24	Correct	78 ms	20788 KB	Output is correct
25	Correct	68 ms	20764 KB	Output is correct
26	Correct	68 ms	20832 KB	Output is correct
27	Runtime error	403 ms	332900 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

답안 #500619

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 0 / 10.0

Subtask #3 0 / 30.0

Subtask #4 0 / 25.0

Subtask #5 0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
0 / 10.0

Subtask #3
0 / 30.0

Subtask #4
0 / 25.0

Subtask #5
0 / 27.0