답안 #49186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49186 2018-05-23T12:04:53 Z aome Vim (BOI13_vim) C++17
100 / 100
85 ms 37072 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 36472 KB Output is correct
2 Correct 28 ms 36580 KB Output is correct
3 Correct 32 ms 36580 KB Output is correct
4 Correct 29 ms 36632 KB Output is correct
5 Correct 28 ms 36680 KB Output is correct
6 Correct 30 ms 36868 KB Output is correct
7 Correct 28 ms 36868 KB Output is correct
8 Correct 27 ms 36868 KB Output is correct
9 Correct 28 ms 36868 KB Output is correct
10 Correct 29 ms 36868 KB Output is correct
11 Correct 31 ms 36868 KB Output is correct
12 Correct 28 ms 36868 KB Output is correct
13 Correct 28 ms 36868 KB Output is correct
14 Correct 28 ms 36868 KB Output is correct
15 Correct 28 ms 36868 KB Output is correct
16 Correct 28 ms 36868 KB Output is correct
17 Correct 30 ms 36868 KB Output is correct
18 Correct 30 ms 36868 KB Output is correct
19 Correct 31 ms 36868 KB Output is correct
20 Correct 28 ms 36868 KB Output is correct
21 Correct 32 ms 36868 KB Output is correct
22 Correct 28 ms 36868 KB Output is correct
23 Correct 30 ms 36868 KB Output is correct
24 Correct 36 ms 36868 KB Output is correct
25 Correct 31 ms 36868 KB Output is correct
26 Correct 35 ms 36868 KB Output is correct
27 Correct 30 ms 36868 KB Output is correct
28 Correct 30 ms 36868 KB Output is correct
29 Correct 34 ms 36868 KB Output is correct
30 Correct 33 ms 36868 KB Output is correct
31 Correct 32 ms 36868 KB Output is correct
32 Correct 28 ms 36868 KB Output is correct
33 Correct 32 ms 36868 KB Output is correct
34 Correct 28 ms 36868 KB Output is correct
35 Correct 31 ms 36868 KB Output is correct
36 Correct 29 ms 36868 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 36868 KB Output is correct
2 Correct 30 ms 36868 KB Output is correct
3 Correct 30 ms 36868 KB Output is correct
4 Correct 35 ms 36868 KB Output is correct
5 Correct 33 ms 36868 KB Output is correct
6 Correct 31 ms 36868 KB Output is correct
7 Correct 33 ms 36868 KB Output is correct
8 Correct 34 ms 36868 KB Output is correct
9 Correct 35 ms 36868 KB Output is correct
10 Correct 33 ms 36868 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 36988 KB Output is correct
2 Correct 57 ms 36988 KB Output is correct
3 Correct 58 ms 37072 KB Output is correct
4 Correct 68 ms 37072 KB Output is correct
5 Correct 61 ms 37072 KB Output is correct
6 Correct 49 ms 37072 KB Output is correct
7 Correct 54 ms 37072 KB Output is correct
8 Correct 55 ms 37072 KB Output is correct
9 Correct 51 ms 37072 KB Output is correct
10 Correct 70 ms 37072 KB Output is correct
11 Correct 64 ms 37072 KB Output is correct
12 Correct 65 ms 37072 KB Output is correct
13 Correct 85 ms 37072 KB Output is correct
14 Correct 66 ms 37072 KB Output is correct
15 Correct 55 ms 37072 KB Output is correct
16 Correct 74 ms 37072 KB Output is correct
17 Correct 61 ms 37072 KB Output is correct
18 Correct 80 ms 37072 KB Output is correct
19 Correct 80 ms 37072 KB Output is correct
20 Correct 55 ms 37072 KB Output is correct