| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49184 |
2018-05-23T09:21:09 Z |
aome |
Vim (BOI13_vim) |
C++17 |
|
28 ms |
7572 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
3560 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
3616 KB |
Output isn't correct |
| 4 |
Correct |
5 ms |
3616 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3616 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3616 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3708 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3732 KB |
Output is correct |
| 9 |
Correct |
5 ms |
3732 KB |
Output is correct |
| 10 |
Correct |
5 ms |
3780 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3780 KB |
Output is correct |
| 12 |
Correct |
5 ms |
3780 KB |
Output is correct |
| 13 |
Correct |
6 ms |
3780 KB |
Output is correct |
| 14 |
Incorrect |
6 ms |
3780 KB |
Output isn't correct |
| 15 |
Incorrect |
6 ms |
3780 KB |
Output isn't correct |
| 16 |
Incorrect |
4 ms |
3848 KB |
Output isn't correct |
| 17 |
Correct |
5 ms |
3848 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3856 KB |
Output is correct |
| 19 |
Incorrect |
5 ms |
3856 KB |
Output isn't correct |
| 20 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 21 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 22 |
Correct |
6 ms |
3856 KB |
Output is correct |
| 23 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 24 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 25 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 26 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 27 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 28 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 29 |
Incorrect |
5 ms |
3856 KB |
Output isn't correct |
| 30 |
Incorrect |
5 ms |
3856 KB |
Output isn't correct |
| 31 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 32 |
Incorrect |
6 ms |
3856 KB |
Output isn't correct |
| 33 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 34 |
Correct |
6 ms |
3856 KB |
Output is correct |
| 35 |
Correct |
5 ms |
3856 KB |
Output is correct |
| 36 |
Correct |
5 ms |
3856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3948 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3956 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3980 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3984 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
4044 KB |
Output isn't correct |
| 6 |
Incorrect |
7 ms |
4160 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
4160 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
4176 KB |
Output isn't correct |
| 9 |
Correct |
9 ms |
4176 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
4176 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
6396 KB |
Output isn't correct |
| 2 |
Incorrect |
17 ms |
6396 KB |
Output isn't correct |
| 3 |
Incorrect |
19 ms |
6500 KB |
Output isn't correct |
| 4 |
Incorrect |
17 ms |
6620 KB |
Output isn't correct |
| 5 |
Incorrect |
20 ms |
6888 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
6888 KB |
Output isn't correct |
| 7 |
Incorrect |
28 ms |
6888 KB |
Output isn't correct |
| 8 |
Incorrect |
18 ms |
6888 KB |
Output isn't correct |
| 9 |
Incorrect |
21 ms |
6888 KB |
Output isn't correct |
| 10 |
Incorrect |
21 ms |
6888 KB |
Output isn't correct |
| 11 |
Incorrect |
17 ms |
7044 KB |
Output isn't correct |
| 12 |
Incorrect |
22 ms |
7372 KB |
Output isn't correct |
| 13 |
Incorrect |
20 ms |
7572 KB |
Output isn't correct |
| 14 |
Incorrect |
19 ms |
7572 KB |
Output isn't correct |
| 15 |
Incorrect |
27 ms |
7572 KB |
Output isn't correct |
| 16 |
Incorrect |
13 ms |
7572 KB |
Output isn't correct |
| 17 |
Incorrect |
17 ms |
7572 KB |
Output isn't correct |
| 18 |
Incorrect |
19 ms |
7572 KB |
Output isn't correct |
| 19 |
Incorrect |
17 ms |
7572 KB |
Output isn't correct |
| 20 |
Incorrect |
25 ms |
7572 KB |
Output isn't correct |
