#include <bits/stdc++.h>
using namespace std;
#define ar array
const int mxN=5e3;
int n, ans, d[mxN][mxN], nxt[mxN+1][10];
string s;
priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> pq;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
fill(nxt[n], nxt[n]+10, n);
for(int i=n-1; ~i; --i) {
memcpy(nxt[i], nxt[i+1], 40);
nxt[i][s[i]-'a']=i;
}
int e=n-1;
while(e&&s[e-1]^'e')
--e;
memset(d, 0x3f, sizeof(d));
d[0][0]=0;
pq.push({0, 0, 0});
while(pq.size()) {
ar<int, 3> u=pq.top();
pq.pop();
if(u[0]>d[u[1]][u[2]])
continue;
if(u[1]>=e) {
ans=u[0];
break;
}
vector<ar<int, 3>> t;
for(int k=0; k<10; ++k)
if(k^4&&nxt[u[2]+1][k]<n)
t.push_back({2, u[1], nxt[u[2]+1][k]});
if(u[2])
t.push_back({1, u[1], u[2]-1});
if(nxt[u[1]+1][4]<u[2]) {
int y=n;
for(int j=0; j<10; ++j)
if(j^4)
y=min(y, nxt[nxt[u[1]+1][4]][j]);
t.push_back({u[2]-nxt[u[1]+1][4], u[2], y});
}
for(ar<int, 3> v : t) {
if(u[0]+v[0]<d[v[1]][v[2]]) {
d[v[1]][v[2]]=u[0]+v[0];
pq.push({u[0]+v[0], v[1], v[2]});
}
}
}
for(char c : s)
ans+=c=='e';
cout << ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
245 ms |
98744 KB |
Output is correct |
| 2 |
Correct |
169 ms |
98744 KB |
Output is correct |
| 3 |
Correct |
159 ms |
98552 KB |
Output is correct |
| 4 |
Correct |
204 ms |
98744 KB |
Output is correct |
| 5 |
Correct |
202 ms |
98680 KB |
Output is correct |
| 6 |
Correct |
282 ms |
98744 KB |
Output is correct |
| 7 |
Correct |
237 ms |
98744 KB |
Output is correct |
| 8 |
Correct |
89 ms |
98168 KB |
Output is correct |
| 9 |
Correct |
82 ms |
98168 KB |
Output is correct |
| 10 |
Correct |
79 ms |
98168 KB |
Output is correct |
| 11 |
Correct |
83 ms |
98252 KB |
Output is correct |
| 12 |
Correct |
80 ms |
98220 KB |
Output is correct |
| 13 |
Correct |
245 ms |
98776 KB |
Output is correct |
| 14 |
Correct |
170 ms |
98744 KB |
Output is correct |
| 15 |
Correct |
138 ms |
98572 KB |
Output is correct |
| 16 |
Correct |
160 ms |
98716 KB |
Output is correct |
| 17 |
Correct |
220 ms |
98732 KB |
Output is correct |
| 18 |
Correct |
176 ms |
98716 KB |
Output is correct |
| 19 |
Correct |
134 ms |
98628 KB |
Output is correct |
| 20 |
Correct |
164 ms |
98744 KB |
Output is correct |
| 21 |
Correct |
187 ms |
98708 KB |
Output is correct |
| 22 |
Correct |
197 ms |
98892 KB |
Output is correct |
| 23 |
Correct |
172 ms |
98552 KB |
Output is correct |
| 24 |
Correct |
162 ms |
98544 KB |
Output is correct |
| 25 |
Correct |
194 ms |
98488 KB |
Output is correct |
| 26 |
Correct |
207 ms |
98716 KB |
Output is correct |
| 27 |
Correct |
238 ms |
98872 KB |
Output is correct |
| 28 |
Correct |
258 ms |
98804 KB |
Output is correct |
| 29 |
Correct |
247 ms |
98748 KB |
Output is correct |
| 30 |
Correct |
193 ms |
98744 KB |
Output is correct |
| 31 |
Correct |
168 ms |
98744 KB |
Output is correct |
| 32 |
Correct |
199 ms |
98940 KB |
Output is correct |
| 33 |
Correct |
184 ms |
98744 KB |
Output is correct |
| 34 |
Correct |
203 ms |
98824 KB |
Output is correct |
| 35 |
Correct |
225 ms |
98772 KB |
Output is correct |
| 36 |
Correct |
256 ms |
98740 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2052 ms |
111180 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2064 ms |
111080 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2060 ms |
108364 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2066 ms |
110936 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2059 ms |
110908 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2059 ms |
101800 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2052 ms |
111064 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2073 ms |
110996 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2061 ms |
110808 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2067 ms |
111120 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
791 ms |
199784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
656 ms |
202768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
461 ms |
199704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
194 ms |
196984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
632 ms |
199344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
340 ms |
199064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
469 ms |
200592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
380 ms |
199192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
206 ms |
196948 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
364 ms |
198688 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
234 ms |
196984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
791 ms |
199212 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
506 ms |
199576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
964 ms |
203044 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
715 ms |
203136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
208 ms |
196948 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
712 ms |
199892 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
441 ms |
199708 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
737 ms |
202704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
616 ms |
202512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
