Submission #49186

#	Time	Username	Problem	Language	Result	Execution time	Memory
49186		aome	Vim (BOI13_vim)	C++17	100 / 100	85 ms	37072 KiB

vim

#include <bits/stdc++.h>

using namespace std;

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

int n;
int cost;
int f1[N][11];
int f2[N][11][11];
bool flag[N];
string s;

void upd(int &x, int y) { x = min(x, y); }

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> s;

	string t = s; s.clear();
	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();

	memset(f1, INF, sizeof f1);
	memset(f2, INF, sizeof f2);

	int x = s[0] - 'a';
	f1[0][x] = f2[0][x][x] = 0;

	for (int i = 1; i <= n; ++i) {
		int x = s[i - 1] - 'a';
		for (int j = 0; j <= 10; ++j) {
			if (j != x && !flag[i - 1]) {
				upd(f1[i][j], f1[i - 1][j]);
			}
			upd(f1[i][j], f1[i - 1][x] + 2);
			if (x != j) {
				upd(f1[i][j], f2[i - 1][x][j]);
			}
			upd(f1[i][j], f2[i - 1][x][x] + 2);
		}
		for (int j = 0; j <= 10; ++j) {
			for (int k = 0; k <= 10; ++k) {
				if (j != x) {
					upd(f2[i][j][k], f1[i - 1][j] + 3);
				}
				upd(f2[i][j][k], f1[i - 1][x] + 5);
				if (j != x && k != x) {
					upd(f2[i][j][k], f2[i - 1][j][k] + 1);
				}
				if (j != x) {
					upd(f2[i][j][k], f2[i - 1][j][x] + 3);
				}
				if (k != x) {
					upd(f2[i][j][k], f2[i - 1][x][k] + 3);
				}
				upd(f2[i][j][k], f2[i - 1][x][x] + 5);
			}
		}
	}

	cout << f1[n][10] + cost - 2;
}

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