| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 601376 |
2022-07-21T19:19:34 Z |
GusterGoose27 |
Vim (BOI13_vim) |
C++11 |
|
298 ms |
150888 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];
int avail[MAXN+1];
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<<9)-1))) 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;
avail[n] = 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;
avail[i] = avail[i+1];
if (elems[i] < 9) avail[i] = i;
}
stree *tree = new stree(0, n-1);
for (int i = n-1; i >= 0; i--) {
if (elems[i] == 9) continue;
if (nextocc[i][9] == n) {
for (int mask = 0; mask < (1<<9); mask++) {
dp[i][mask] = 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], dq[nextpos]+nextpos-i+2);
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(avail[le]+1, 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 |
2 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1108 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 17 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 18 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 22 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 25 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 26 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 27 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 28 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 30 |
Incorrect |
2 ms |
1364 KB |
Output isn't correct |
| 31 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 32 |
Incorrect |
2 ms |
1352 KB |
Output isn't correct |
| 33 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 34 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 35 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 36 |
Correct |
2 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9712 KB |
Output is correct |
| 2 |
Correct |
17 ms |
11000 KB |
Output is correct |
| 3 |
Correct |
9 ms |
5940 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9684 KB |
Output is correct |
| 5 |
Incorrect |
17 ms |
10860 KB |
Output isn't correct |
| 6 |
Incorrect |
21 ms |
10964 KB |
Output isn't correct |
| 7 |
Incorrect |
16 ms |
10376 KB |
Output isn't correct |
| 8 |
Incorrect |
15 ms |
10240 KB |
Output isn't correct |
| 9 |
Correct |
20 ms |
11092 KB |
Output is correct |
| 10 |
Incorrect |
18 ms |
11036 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
130124 KB |
Output isn't correct |
| 2 |
Incorrect |
224 ms |
127348 KB |
Output isn't correct |
| 3 |
Incorrect |
253 ms |
130668 KB |
Output isn't correct |
| 4 |
Incorrect |
241 ms |
150860 KB |
Output isn't correct |
| 5 |
Incorrect |
298 ms |
150508 KB |
Output isn't correct |
| 6 |
Incorrect |
149 ms |
115924 KB |
Output isn't correct |
| 7 |
Incorrect |
226 ms |
137412 KB |
Output isn't correct |
| 8 |
Incorrect |
272 ms |
140268 KB |
Output isn't correct |
| 9 |
Incorrect |
197 ms |
133444 KB |
Output isn't correct |
| 10 |
Incorrect |
198 ms |
132684 KB |
Output isn't correct |
| 11 |
Incorrect |
268 ms |
150888 KB |
Output isn't correct |
| 12 |
Incorrect |
279 ms |
150212 KB |
Output isn't correct |
| 13 |
Incorrect |
266 ms |
145712 KB |
Output isn't correct |
| 14 |
Incorrect |
265 ms |
147536 KB |
Output isn't correct |
| 15 |
Incorrect |
242 ms |
149068 KB |
Output isn't correct |
| 16 |
Incorrect |
245 ms |
128460 KB |
Output isn't correct |
| 17 |
Incorrect |
247 ms |
130124 KB |
Output isn't correct |
| 18 |
Incorrect |
243 ms |
130668 KB |
Output isn't correct |
| 19 |
Incorrect |
229 ms |
127436 KB |
Output isn't correct |
| 20 |
Incorrect |
209 ms |
129000 KB |
Output isn't correct |
