Submission #1247818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247818		kaiboy	Vim (BOI13_vim)	C++20	100 / 100	20 ms	556 KiB

vim

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 70000;
const int   A = 10;
const int INF = 0x3f3f3f3f;

char aa[N + 1];
bool ee[N + 1];
int dp[A][A + 1], dq[A][A + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> aa;
	int k = 0, m = 0; bool e = false;
	for (int i = 0; i < n; i++)
		if (aa[i] == 'e')
			k += 2, e = true;
		else
			aa[m] = aa[i] - 'a' - (aa[i] > 'e'), ee[m] = e, m++, e = false;
	n = m;
	for (int a = 0; a < A; a++) {
		for (int b = 0; b <= A; b++)
			dp[a][b] = INF;
		dp[a][A] = 2;
	}
	for (int i = 1; i < n; i++) {
		for (int a = 0; a < A; a++)
			for (int b = 0; b <= A; b++)
				dq[a][b] = INF;
		for (int a = 0; a < A; a++)
			for (int b = 0; b <= A; b++) {
				int x = dp[a][b];
				if (x == INF)
					continue;
				if (b == A) {
					if (a == aa[i])
						for (int c = 0; c < A; c++)
							dq[c][A] = min(dq[c][A], x + 2);
					else if (!ee[i])
						dq[a][A] = min(dq[a][A], x);
					else
						for (int c = 0; c < A; c++)
							dq[c][a] = min(dq[c][a], x + 2);
				} else {
					x++;
					if (a == aa[i]) {
						for (int c = 0; c < A; c++)
							if (b == aa[i])
								for (int d = 0; d <= A; d++)
									dq[c][d] = min(dq[c][d], x + 2 + (d < A ? 2 : 0));
							else
								dq[c][b] = min(dq[c][b], x + 2);
					} else {
						if (b == aa[i])
							for (int d = 0; d <= A; d++)
								dq[a][d] = min(dq[a][d], x + (d < A ? 2 : 0));
						else
							dq[a][b] = min(dq[a][b], x);
					}
				}
			}
		for (int a = 0; a < A; a++)
			for (int b = 0; b <= A; b++)
				dp[a][b] = dq[a][b];
	}
	cout << k + dp[A - 1][A] - 2 << '\n';
	return 0;
}

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