Submission #49184

#	Time	Username	Problem	Language	Result	Execution time	Memory
49184		aome	Vim (BOI13_vim)	C++17	42.50 / 100	28 ms	7572 KiB

vim

#include <bits/stdc++.h>

using namespace std;

const int N = 70005;
const int INF = 0x3f3f3f3f;

int n;
int cost;
int a[N];
int b[N][11];
int f[N][11];
bool flag[N];
string s;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> s;
	string t = s; s.clear();
	flag[0] = 1;
	for (int i = 0; i < n; ++i) {
		if (t[i] == 'e') flag[s.size()] = 1, cost += 2;
		else s.push_back(t[i]); 
	}
	n = s.size();
	int cur = n;
	for (int i = n - 1; i >= 0; --i) {
		a[i] = cur; if (flag[i]) cur = i;
	}
	for (int i = 0; i < 10; ++i) {
		int cur = n;
		for (int j = n - 1; j >= 0; --j) {
			b[j][i] = cur;
			if (s[j] - 'a' == i) cur = j;
		}
	}
	memset(f, INF, sizeof f);
	int res = INF; f[0][10] = 0;
	// cout << s << '\n';
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= 10; ++j) {
			if (f[i][j] == INF) continue;
			// cout << i << ' ' << j << ' ' << f[i][j] << '\n';
			if (j == 10) {
				if (a[i] == n) res = min(res, f[i][j]);
			}
			else {
				if (a[b[i][j]] == n) res = min(res, f[i][j]);
			}
			for (int k = 0; k < 10; ++k) {
				int x = b[i][k];
				if (x == n) continue;
				int y;
				if (j == 10) y = a[i];
				else {
					if (x < b[i][j]) continue;
					y = a[b[i][j]];
				}
				if (y >= x) f[x][10] = min(f[x][10], f[i][j] + 2);
				else {
					f[y][k] = min(f[y][k], f[i][j] + 2 + x - y);
				}
			}
		}
	}
	cout << res + cost;
}

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