| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 544609 |
2022-04-02T13:34:15 Z |
rainboy |
Vim (BOI13_vim) |
C |
|
41 ms |
22520 KB |
/* upsolve using analysis */
#include <stdio.h>
#include <string.h>
#define N 70000
#define A 10
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int main() {
static char cc[N + 1], must[N + 1];
static int dp[N + 1][A], dq[N + 1][A][A];
int n, n_, i, a, b, a_, b_, e, ans;
scanf("%d%s", &n, cc), n = strlen(cc);
n_ = 0, e = 1, ans = 0;
for (i = 0; i < n; i++)
if (cc[i] != 'e') {
cc[n_] = cc[i], must[n_] = e, n_++;
e = 0;
} else {
ans += n_ == 0 ? 1 : 2;
e = 1;
}
cc[n_++] = 'e';
n = n_;
cc[n] = 0;
for (i = 0; i < n; i++) {
memset(dp[i], 0x3f, sizeof dp[i]);
memset(dq[i], 0x3f, sizeof dq[i]);
}
dp[0][cc[0] - 'a'] = 0;
for (i = 0; i + 1 < n; i++) {
int c = cc[i] - 'a';
for (a = 0; a < A; a++) {
int x = dp[i][a];
if (x == INF)
continue;
if (a != c) {
if (!must[i])
dp[i + 1][a] = min(dp[i + 1][a], x);
for (b = 0; b < A; b++)
dq[i + 1][a][b] = min(dq[i + 1][a][b], x + 3);
} else
for (a_ = 0; a_ < A; a_++) {
dp[i + 1][a_] = min(dp[i + 1][a_], x + 2);
for (b_ = 0; b_ < A; b_++)
dq[i + 1][a_][b_] = min(dq[i + 1][a_][b_], x + 5);
}
}
for (a = 0; a < A; a++)
for (b = 0; b < A; b++) {
int x = dq[i][a][b];
if (x == INF)
continue;
if (a != c && b != c)
dq[i + 1][a][b] = min(dq[i + 1][a][b], x + 1);
else if (a != c && b == c)
for (b_ = 0; b_ < A; b_++)
dq[i + 1][a][b_] = min(dq[i + 1][a][b_], x + 3);
else if (a == c && b != c) {
dp[i + 1][b] = min(dp[i + 1][b], x);
for (a_ = 0; a_ < A; a_++)
dq[i + 1][a_][b] = min(dq[i + 1][a_][b], x + 3);
} else
for (b_ = 0; b_ < A; b_++) {
dp[i + 1][b_] = min(dp[i + 1][b_], x + 2);
for (a_ = 0; a_ < A; a_++)
dq[i + 1][a_][b_] = min(dq[i + 1][a_][b_], x + 5);
}
}
}
ans += dp[n - 1][4] - 2;
printf("%d\n", ans);
return 0;
}
Compilation message
vim.c: In function 'main':
vim.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d%s", &n, cc), n = strlen(cc);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
292 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
0 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
468 KB |
Output is correct |
| 24 |
Correct |
1 ms |
424 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
424 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
1 ms |
468 KB |
Output is correct |
| 33 |
Correct |
1 ms |
340 KB |
Output is correct |
| 34 |
Correct |
1 ms |
420 KB |
Output is correct |
| 35 |
Correct |
0 ms |
340 KB |
Output is correct |
| 36 |
Correct |
1 ms |
420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
852 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1832 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1456 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
19540 KB |
Output is correct |
| 2 |
Correct |
35 ms |
18772 KB |
Output is correct |
| 3 |
Correct |
36 ms |
19796 KB |
Output is correct |
| 4 |
Correct |
36 ms |
20180 KB |
Output is correct |
| 5 |
Correct |
41 ms |
22504 KB |
Output is correct |
| 6 |
Correct |
19 ms |
10296 KB |
Output is correct |
| 7 |
Correct |
31 ms |
16884 KB |
Output is correct |
| 8 |
Correct |
38 ms |
19632 KB |
Output is correct |
| 9 |
Correct |
26 ms |
14516 KB |
Output is correct |
| 10 |
Correct |
26 ms |
13884 KB |
Output is correct |
| 11 |
Correct |
36 ms |
20180 KB |
Output is correct |
| 12 |
Correct |
40 ms |
22520 KB |
Output is correct |
| 13 |
Correct |
40 ms |
22100 KB |
Output is correct |
| 14 |
Correct |
40 ms |
21716 KB |
Output is correct |
| 15 |
Correct |
34 ms |
18260 KB |
Output is correct |
| 16 |
Correct |
36 ms |
19896 KB |
Output is correct |
| 17 |
Correct |
36 ms |
19568 KB |
Output is correct |
| 18 |
Correct |
36 ms |
19796 KB |
Output is correct |
| 19 |
Correct |
35 ms |
18828 KB |
Output is correct |
| 20 |
Correct |
31 ms |
15828 KB |
Output is correct |
