| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 248789 | 2020-07-13T11:56:51 Z | mieszko11b | Vim (BOI13_vim) | C++14 | 663 ms | 205560 KB |
#include <bits/stdc++.h>
using namespace std;
int n;
char c[70007];
int pre[70007];
int nxt[10][70007];
int dp[5007][5007]; // ostatni usuniety, pozycja kursora
int main() {
scanf("%d", &n);
scanf(" %s", c + 1);
int cnte = 0;
for(int i = 1 ; i <= n ; i++) {
if(c[i] == 'e')
pre[i] = i, cnte++;
else
pre[i] = pre[i - 1];
}
for(int i = n - 1 ; i >= 0 ; i--) {
for(char cc = 'a' ; cc <= 'j' ; cc++) {
if(c[i + 1] == cc)
nxt[cc - 'a'][i] = i + 1;
else
nxt[cc - 'a'][i] = nxt[cc - 'a'][i + 1];
}
}
for(int i = 0 ; i < 5005 ; i++)
for(int j = 0 ; j < 5005 ; j++)
dp[i][j] = 1e9;
dp[0][1] = cnte;
for(int i = 0 ; i < n ; i++) {
if(i == 0 || c[i] == 'e') {
for(int j = 1 ; j <= n ; j++) {
if(j < n) {
for(int k = 0 ; k < 10 ; k++)
if(k != 4 && nxt[k][j])
dp[i][nxt[k][j]] = min(dp[i][nxt[k][j]], dp[i][j] + 2);
}
if(pre[j] > i)
dp[pre[j]][nxt[4][i] + 1] = min(dp[pre[j]][nxt[4][i] + 1],
dp[i][j] + j - nxt[4][i]);
}
}
}
int res = 1e9;
for(int j = 1 ; j <= n ; j++)
res = min(res, dp[pre[n]][j]);
printf("%d\n", res);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 64 ms | 98424 KB | Output is correct |
| 2 | Correct | 74 ms | 98424 KB | Output is correct |
| 3 | Correct | 62 ms | 98424 KB | Output is correct |
| 4 | Correct | 72 ms | 98424 KB | Output is correct |
| 5 | Correct | 65 ms | 98424 KB | Output is correct |
| 6 | Correct | 63 ms | 98424 KB | Output is correct |
| 7 | Correct | 64 ms | 98424 KB | Output is correct |
| 8 | Correct | 58 ms | 98424 KB | Output is correct |
| 9 | Correct | 59 ms | 98424 KB | Output is correct |
| 10 | Correct | 58 ms | 98392 KB | Output is correct |
| 11 | Correct | 60 ms | 98424 KB | Output is correct |
| 12 | Correct | 59 ms | 98424 KB | Output is correct |
| 13 | Correct | 64 ms | 98424 KB | Output is correct |
| 14 | Correct | 62 ms | 98424 KB | Output is correct |
| 15 | Correct | 60 ms | 98424 KB | Output is correct |
| 16 | Correct | 63 ms | 98424 KB | Output is correct |
| 17 | Correct | 64 ms | 98424 KB | Output is correct |
| 18 | Correct | 62 ms | 98424 KB | Output is correct |
| 19 | Correct | 64 ms | 98424 KB | Output is correct |
| 20 | Correct | 62 ms | 98424 KB | Output is correct |
| 21 | Correct | 62 ms | 98424 KB | Output is correct |
| 22 | Correct | 62 ms | 98524 KB | Output is correct |
| 23 | Correct | 63 ms | 98424 KB | Output is correct |
| 24 | Correct | 60 ms | 98424 KB | Output is correct |
| 25 | Correct | 61 ms | 98424 KB | Output is correct |
| 26 | Correct | 62 ms | 98492 KB | Output is correct |
| 27 | Correct | 64 ms | 98424 KB | Output is correct |
| 28 | Correct | 63 ms | 98516 KB | Output is correct |
| 29 | Correct | 67 ms | 98552 KB | Output is correct |
| 30 | Correct | 63 ms | 98424 KB | Output is correct |
| 31 | Correct | 62 ms | 98424 KB | Output is correct |
| 32 | Correct | 62 ms | 98424 KB | Output is correct |
| 33 | Correct | 62 ms | 98424 KB | Output is correct |
| 34 | Correct | 63 ms | 98452 KB | Output is correct |
| 35 | Correct | 65 ms | 98424 KB | Output is correct |
| 36 | Correct | 63 ms | 98540 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 654 ms | 98680 KB | Output isn't correct |
| 2 | Correct | 515 ms | 98836 KB | Output is correct |
| 3 | Incorrect | 219 ms | 98552 KB | Output isn't correct |
| 4 | Incorrect | 663 ms | 98680 KB | Output isn't correct |
| 5 | Correct | 476 ms | 98680 KB | Output is correct |
| 6 | Correct | 317 ms | 98680 KB | Output is correct |
| 7 | Incorrect | 552 ms | 98680 KB | Output isn't correct |
| 8 | Incorrect | 546 ms | 98680 KB | Output isn't correct |
| 9 | Correct | 522 ms | 98724 KB | Output is correct |
| 10 | Correct | 460 ms | 98808 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 167 ms | 204604 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 168 ms | 204572 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 175 ms | 204792 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Runtime error | 175 ms | 205560 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 | Runtime error | 171 ms | 205480 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 181 ms | 204940 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 169 ms | 205048 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Runtime error | 173 ms | 205048 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 | Runtime error | 193 ms | 205112 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Runtime error | 170 ms | 205304 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Runtime error | 174 ms | 205432 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 | Runtime error | 177 ms | 205432 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Runtime error | 234 ms | 205304 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 | Runtime error | 182 ms | 205432 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 | Runtime error | 179 ms | 205560 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 | Runtime error | 167 ms | 204664 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 | Runtime error | 169 ms | 204668 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 | Runtime error | 175 ms | 204792 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 | Runtime error | 166 ms | 204668 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 | Runtime error | 181 ms | 204664 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |