Submission #1247617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247617		kaiboy	Vim (BOI13_vim)	C++20	60 / 100	367 ms	98468 KiB

vim

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

using namespace std;

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

char aa[N + 1];
int qq[N][A], dp[N][N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> aa;
	for (int i = n - 1; i >= 0; i--) {
		aa[i] -= 'a';
		if (i + 1 < n) {
			for (int a = 0; a < A; a++)
				qq[i][a] = qq[i + 1][a];
			qq[i][(int) aa[i + 1]] = i + 1;
		} else
			for (int a = 0; a < A; a++)
				qq[i][a] = n;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dp[i][j] = INF;
	dp[0][0] = 0;
	for (int j = 0; j < n; j++)
		for (int i = 0; i < n; i++) {
			int x = dp[i][j];
			if (x == INF)
				continue;
			for (int a = 0; a < A; a++)
				if (a != 4) {
					int i_ = qq[i][a];
					if (i_ < n)
						dp[i_][j] = min(dp[i_][j], x + 2);
				}
			int i_ = qq[j][4];
			if (i_ > i)
				continue;
			int i__ = i + 1;
			for (int a = 0; a < A; a++)
				if (a != 4)
					i__ = min(i__, qq[i_][a]);
			dp[i__][i] = min(dp[i__][i], x + i - i_);
		}
	int ans = INF;
	for (int j = n - 1; j >= 0; j--) {
		for (int i = 0; i <= j; i++)
			ans = min(ans, dp[i][j]);
		if (aa[j] == 4)
			break;
	}
	for (int i = 0; i < n; i++)
		if (aa[i] == 4)
			ans++;
	cout << ans << '\n';
	return 0;
}

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