#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=7e4+7, INF=1e9+7;
int nxt[LIM][10], odl[LIM][10], kiedy[10];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, e=0;
string s;
cin >> n >> s;
rep(i, n) {
if(s[i]=='e') {
s[i]='a';
++e;
} else if(s[i]=='a') s[i]='e';
}
string xd="";
xd+=s[0];
for(int i=1; i<n; ++i) if(xd.back()!='a' || s[i]!='a') xd+=s[i];
s=xd;
n=s.size();
rep(i, 10) kiedy[i]=INF;
for(int i=n-1; i>=0; --i) {
rep(j, 10) {
nxt[i][j]=kiedy[j];
odl[i][j]=INF;
}
kiedy[s[i]-'a']=i;
}
priority_queue<pair<int,pair<int,int>>>q;
q.push({0, {0, 0}});
while(!q.empty()) {
int o=-q.top().st, a=q.top().nd.st, b=q.top().nd.nd; q.pop();
if(o>=odl[a][b]) continue;
odl[a][b]=o;
int p=nxt[a][b];
if(!b) p=a;
if(nxt[p][0]==INF) {
cout << o+e << '\n';
break;
}
for(int i=1; i<10; ++i) if(nxt[a][i]<INF && nxt[a][i]>=p) {
if(nxt[p][0]>nxt[a][i]) {
if(odl[nxt[a][i]][i]==INF) q.push({-o-2, {nxt[a][i], 0}});
} else {
int c=i;
if(nxt[p][0]+1==nxt[a][i]) c=0;
if(odl[nxt[p][0]+1][c]==INF) q.push({-o-2-nxt[a][i]+nxt[p][0], {nxt[p][0]+1, c}});
}
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 9 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 16 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 17 |
Correct |
2 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
2 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
324 KB |
Output is correct |
| 24 |
Correct |
1 ms |
324 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
2 ms |
332 KB |
Output is correct |
| 29 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 30 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 33 |
Correct |
1 ms |
332 KB |
Output is correct |
| 34 |
Correct |
2 ms |
332 KB |
Output is correct |
| 35 |
Correct |
2 ms |
380 KB |
Output is correct |
| 36 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
652 KB |
Output isn't correct |
| 2 |
Correct |
17 ms |
716 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
536 KB |
Output isn't correct |
| 4 |
Incorrect |
11 ms |
588 KB |
Output isn't correct |
| 5 |
Incorrect |
16 ms |
1040 KB |
Output isn't correct |
| 6 |
Incorrect |
11 ms |
1168 KB |
Output isn't correct |
| 7 |
Incorrect |
11 ms |
712 KB |
Output isn't correct |
| 8 |
Incorrect |
11 ms |
700 KB |
Output isn't correct |
| 9 |
Correct |
15 ms |
772 KB |
Output is correct |
| 10 |
Incorrect |
12 ms |
768 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
183 ms |
8416 KB |
Output isn't correct |
| 2 |
Incorrect |
85 ms |
5208 KB |
Output isn't correct |
| 3 |
Incorrect |
111 ms |
5324 KB |
Output isn't correct |
| 4 |
Incorrect |
113 ms |
7720 KB |
Output isn't correct |
| 5 |
Incorrect |
169 ms |
9220 KB |
Output isn't correct |
| 6 |
Incorrect |
124 ms |
3824 KB |
Output isn't correct |
| 7 |
Incorrect |
197 ms |
8768 KB |
Output isn't correct |
| 8 |
Incorrect |
167 ms |
8876 KB |
Output isn't correct |
| 9 |
Incorrect |
166 ms |
6380 KB |
Output isn't correct |
| 10 |
Incorrect |
156 ms |
4676 KB |
Output isn't correct |
| 11 |
Incorrect |
121 ms |
7712 KB |
Output isn't correct |
| 12 |
Incorrect |
171 ms |
9324 KB |
Output isn't correct |
| 13 |
Incorrect |
119 ms |
5984 KB |
Output isn't correct |
| 14 |
Incorrect |
98 ms |
5964 KB |
Output isn't correct |
| 15 |
Incorrect |
194 ms |
6112 KB |
Output isn't correct |
| 16 |
Incorrect |
93 ms |
6824 KB |
Output isn't correct |
| 17 |
Incorrect |
154 ms |
8424 KB |
Output isn't correct |
| 18 |
Incorrect |
108 ms |
5324 KB |
Output isn't correct |
| 19 |
Incorrect |
87 ms |
5196 KB |
Output isn't correct |
| 20 |
Incorrect |
164 ms |
5260 KB |
Output isn't correct |
