Submission #544609

#	Time	Username	Problem	Language	Result	Execution time	Memory
544609		rainboy	Vim (BOI13_vim)	C11	100 / 100	41 ms	22520 KiB

vim

/* upsolve using analysis */
#include <stdio.h>
#include <string.h>

#define N	70000
#define A	10
#define INF	0x3f3f3f3f

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

int main() {
	static char cc[N + 1], must[N + 1];
	static int dp[N + 1][A], dq[N + 1][A][A];
	int n, n_, i, a, b, a_, b_, e, ans;

	scanf("%d%s", &n, cc), n = strlen(cc);
	n_ = 0, e = 1, ans = 0;
	for (i = 0; i < n; i++)
		if (cc[i] != 'e') {
			cc[n_] = cc[i], must[n_] = e, n_++;
			e = 0;
		} else {
			ans += n_ == 0 ? 1 : 2;
			e = 1;
		}
	cc[n_++] = 'e';
	n = n_;
	cc[n] = 0;
	for (i = 0; i < n; i++) {
		memset(dp[i], 0x3f, sizeof dp[i]);
		memset(dq[i], 0x3f, sizeof dq[i]);
	}
	dp[0][cc[0] - 'a'] = 0;
	for (i = 0; i + 1 < n; i++) {
		int c = cc[i] - 'a';

		for (a = 0; a < A; a++) {
			int x = dp[i][a];

			if (x == INF)
				continue;
			if (a != c) {
				if (!must[i])
					dp[i + 1][a] = min(dp[i + 1][a], x);
				for (b = 0; b < A; b++)
					dq[i + 1][a][b] = min(dq[i + 1][a][b], x + 3);
			} else
				for (a_ = 0; a_ < A; a_++) {
					dp[i + 1][a_] = min(dp[i + 1][a_], x + 2);
					for (b_ = 0; b_ < A; b_++)
						dq[i + 1][a_][b_] = min(dq[i + 1][a_][b_], x + 5);
				}
		}
		for (a = 0; a < A; a++)
			for (b = 0; b < A; b++) {
				int x = dq[i][a][b];

				if (x == INF)
					continue;
				if (a != c && b != c)
					dq[i + 1][a][b] = min(dq[i + 1][a][b], x + 1);
				else if (a != c && b == c)
					for (b_ = 0; b_ < A; b_++)
						dq[i + 1][a][b_] = min(dq[i + 1][a][b_], x + 3);
				else if (a == c && b != c) {
					dp[i + 1][b] = min(dp[i + 1][b], x);
					for (a_ = 0; a_ < A; a_++)
						dq[i + 1][a_][b] = min(dq[i + 1][a_][b], x + 3);
				} else
					for (b_ = 0; b_ < A; b_++) {
						dp[i + 1][b_] = min(dp[i + 1][b_], x + 2);
						for (a_ = 0; a_ < A; a_++)
							dq[i + 1][a_][b_] = min(dq[i + 1][a_][b_], x + 5);
					}
			}
	}
	ans += dp[n - 1][4] - 2;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

vim.c: In function 'main':
vim.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%s", &n, cc), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40