Submission #500619

#	Time	Username	Problem	Language	Result	Execution time	Memory
500619		rainboy	Tortoise (CEOI21_tortoise)	C11	8 / 100	403 ms	332900 KiB

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 (stderr)

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 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27