#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 << 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;
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";
}
Compilation message
vim.cpp: In function 'void make_dp(int, int, int, int)':
vim.cpp:54:30: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
54 | if (mask & (1 << elems[i]) == 0) other = 2+dp[i][(1<<9)-1];
| ~~~~~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 5 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
1364 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
1364 KB |
Output isn't correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
1108 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 17 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 18 |
Incorrect |
2 ms |
1108 KB |
Output isn't correct |
| 19 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 21 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 22 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 23 |
Incorrect |
2 ms |
1364 KB |
Output isn't correct |
| 24 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 25 |
Correct |
2 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 |
Incorrect |
2 ms |
1364 KB |
Output isn't 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 |
3 ms |
1364 KB |
Output isn't correct |
| 33 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 34 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 35 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 36 |
Incorrect |
2 ms |
1364 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
9664 KB |
Output isn't correct |
| 2 |
Incorrect |
16 ms |
11068 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
5940 KB |
Output isn't correct |
| 4 |
Incorrect |
12 ms |
9684 KB |
Output isn't correct |
| 5 |
Incorrect |
17 ms |
10904 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
10964 KB |
Output isn't correct |
| 7 |
Incorrect |
15 ms |
10316 KB |
Output isn't correct |
| 8 |
Incorrect |
15 ms |
10196 KB |
Output isn't correct |
| 9 |
Incorrect |
17 ms |
11060 KB |
Output isn't correct |
| 10 |
Incorrect |
21 ms |
11100 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
263 ms |
130044 KB |
Output isn't correct |
| 2 |
Incorrect |
215 ms |
127416 KB |
Output isn't correct |
| 3 |
Incorrect |
248 ms |
130676 KB |
Output isn't correct |
| 4 |
Incorrect |
243 ms |
150764 KB |
Output isn't correct |
| 5 |
Incorrect |
276 ms |
150160 KB |
Output isn't correct |
| 6 |
Incorrect |
153 ms |
115916 KB |
Output isn't correct |
| 7 |
Incorrect |
223 ms |
137536 KB |
Output isn't correct |
| 8 |
Incorrect |
258 ms |
140212 KB |
Output isn't correct |
| 9 |
Incorrect |
204 ms |
133396 KB |
Output isn't correct |
| 10 |
Incorrect |
196 ms |
132760 KB |
Output isn't correct |
| 11 |
Incorrect |
247 ms |
150816 KB |
Output isn't correct |
| 12 |
Incorrect |
272 ms |
150136 KB |
Output isn't correct |
| 13 |
Incorrect |
266 ms |
145792 KB |
Output isn't correct |
| 14 |
Incorrect |
258 ms |
147520 KB |
Output isn't correct |
| 15 |
Incorrect |
237 ms |
149152 KB |
Output isn't correct |
| 16 |
Incorrect |
232 ms |
128668 KB |
Output isn't correct |
| 17 |
Incorrect |
238 ms |
130068 KB |
Output isn't correct |
| 18 |
Incorrect |
234 ms |
130636 KB |
Output isn't correct |
| 19 |
Incorrect |
213 ms |
127332 KB |
Output isn't correct |
| 20 |
Incorrect |
221 ms |
129008 KB |
Output isn't correct |
