| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 601349 |
2022-07-21T18:07:11 Z |
GusterGoose27 |
Vim (BOI13_vim) |
C++11 |
|
401 ms |
150660 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 70000;
const int inf = 1e9;
int n;
int dp[MAXN][1 << 9]; // dont return to i
int dq[MAXN]; // return to i
int elems[MAXN];
int nextocc[MAXN][10];
bool ise[MAXN];
int nextdp[9];
class stree {
public:
stree *l = nullptr;
stree *r = nullptr;
int lp, rp;
int mne;
int cont_mask = 0;
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp == rp) {
if (ise[lp]) mne = lp;
else mne = n;
if (elems[lp] < 9) cont_mask = (1 << elems[lp]);
}
else {
int m = (lp+rp)/2;
l = new stree(lp, m);
r = new stree(m+1, rp);
mne = min(l->mne, r->mne);
cont_mask = l->cont_mask | r->cont_mask;
}
}
int query(int lv, int rv) {
if (lp > rv || rp < lv) return n;
if (lp >= lv && rp <= rv) return mne;
return min(l->query(lv, rv), r->query(lv, rv));
}
int get_cont(int lv, int rv) {
if (lp > rv || rp < lv) return 0;
if (lp >= lv && rp <= rv) return cont_mask;
return l->get_cont(lv, rv) | r->get_cont(lv, rv);
}
};
void make_dp(int i, int pos = 0, int mask = 0, int best = inf) {
if (pos == 9) {
int other = inf;
if ((mask & (1 << elems[i])) == 0) other = 2+dp[i][(1<<9)-1];
dp[i][mask] = min(other, best);
return;
}
make_dp(i, pos+1, mask+(1<<pos), min(best, nextdp[pos]));
make_dp(i, pos+1, mask, best);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
string s; cin >> s;
int nume = 0;
for (int i = 0; i < n; i++) {
int v = s[i]-'a';
if (v == 4) {
ise[i] = 1;
v = 10;
}
if (v > 4) v--;
elems[i] = v;
nume += ise[i];
}
int seen[10];
for (int i = 0; i < 10; i++) seen[i] = n;
for (int i = n-1; i >= 0; i--) {
for (int j = 0; j < 10; j++) nextocc[i][j] = seen[j];
seen[elems[i]] = i;
}
stree *tree = new stree(0, n-1);
for (int i = n-1; i >= 0; i--) {
if (nextocc[i][9] == n) {
for (int mask = 0; mask < (1<<9); mask++) {
dp[i][mask] = 0;
}
dq[i] = 0;
dq[i] = 0;
continue;
}
dq[i] = inf;
for (int j = 0; j < 9; j++) {
int nextpos = nextocc[i][j];
if (nextpos == n) {
nextdp[j] = inf;
continue;
}
dq[i] = min(dq[i], 2+dq[nextpos]+nextpos-i);
int le = tree->query(i, nextpos);
if (le == n) {
nextdp[j] = 2+dp[nextpos][(1 << 9)-1];
continue;
}
nextdp[j] = 2+nextpos-le;
if (nextocc[nextpos][9] == n) continue;
int allow = ((1 << 9)-1)^(tree->get_cont(le, nextpos));
nextdp[j] += min(dq[nextpos], dp[nextpos][allow]);
}
make_dp(i);
}
cout << (nume+dp[0][(1 << 9)-1]) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
1108 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 5 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
1352 KB |
Output isn't correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 14 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 15 |
Incorrect |
3 ms |
1108 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 17 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
1108 KB |
Output isn't correct |
| 19 |
Correct |
2 ms |
980 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 21 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 22 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 23 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 24 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 25 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 26 |
Incorrect |
3 ms |
1224 KB |
Output isn't correct |
| 27 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 28 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 29 |
Incorrect |
3 ms |
1352 KB |
Output isn't correct |
| 30 |
Incorrect |
3 ms |
1356 KB |
Output isn't correct |
| 31 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 32 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 33 |
Incorrect |
3 ms |
1364 KB |
Output isn't correct |
| 34 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 35 |
Incorrect |
3 ms |
1228 KB |
Output isn't correct |
| 36 |
Incorrect |
3 ms |
1360 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
10964 KB |
Output isn't correct |
| 2 |
Incorrect |
27 ms |
11012 KB |
Output isn't correct |
| 3 |
Incorrect |
15 ms |
6356 KB |
Output isn't correct |
| 4 |
Incorrect |
26 ms |
10828 KB |
Output isn't correct |
| 5 |
Incorrect |
27 ms |
10828 KB |
Output isn't correct |
| 6 |
Incorrect |
28 ms |
11036 KB |
Output isn't correct |
| 7 |
Incorrect |
30 ms |
11016 KB |
Output isn't correct |
| 8 |
Incorrect |
26 ms |
10764 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
10948 KB |
Output isn't correct |
| 10 |
Incorrect |
25 ms |
10948 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
321 ms |
129924 KB |
Output isn't correct |
| 2 |
Incorrect |
285 ms |
127232 KB |
Output isn't correct |
| 3 |
Incorrect |
318 ms |
130468 KB |
Output isn't correct |
| 4 |
Incorrect |
343 ms |
150644 KB |
Output isn't correct |
| 5 |
Incorrect |
401 ms |
149920 KB |
Output isn't correct |
| 6 |
Incorrect |
329 ms |
132272 KB |
Output isn't correct |
| 7 |
Incorrect |
366 ms |
137308 KB |
Output isn't correct |
| 8 |
Incorrect |
352 ms |
139976 KB |
Output isn't correct |
| 9 |
Incorrect |
364 ms |
138808 KB |
Output isn't correct |
| 10 |
Incorrect |
349 ms |
140556 KB |
Output isn't correct |
| 11 |
Incorrect |
400 ms |
150660 KB |
Output isn't correct |
| 12 |
Incorrect |
364 ms |
149972 KB |
Output isn't correct |
| 13 |
Incorrect |
347 ms |
145560 KB |
Output isn't correct |
| 14 |
Incorrect |
334 ms |
147260 KB |
Output isn't correct |
| 15 |
Incorrect |
367 ms |
148900 KB |
Output isn't correct |
| 16 |
Incorrect |
306 ms |
128344 KB |
Output isn't correct |
| 17 |
Incorrect |
320 ms |
129904 KB |
Output isn't correct |
| 18 |
Incorrect |
322 ms |
130528 KB |
Output isn't correct |
| 19 |
Incorrect |
282 ms |
127236 KB |
Output isn't correct |
| 20 |
Incorrect |
315 ms |
128836 KB |
Output isn't correct |
