| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 243081 |
2020-06-30T09:16:26 Z |
ffao |
Vim (BOI13_vim) |
C++14 |
|
2000 ms |
266248 KB |
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int n;
string s;
#define JMPS 20
int ccE;
int nxtnE[71000];
int nxt[71000][21];
int idxE[71000];
int jmp[71000][21][21];
int dist[71000][21][21];
priority_queue< pair<int, pair<int, pii> > > q;
void update(int nextE, int let, int idx, int curDist) {
if (dist[nextE][let][idx] > curDist) {
dist[nextE][let][idx] = curDist;
q.push( {-curDist, {nextE, {let, idx}}} );
}
}
void expand(int curPos, int nextE, int curDist) {
// cout << "EXP" << endl;
for (int letdst = 0; letdst < 10; letdst++) if (letdst != 4) {
for (int idx = 0; idx < JMPS; idx++) if (jmp[nextE][letdst][idx+1] != n) {
int dest = jmp[nextE][letdst][idx+1];
int pos = curPos, tDist = curDist;
while (pos < dest) {
int nP = pos;
for (int tt = 0; tt < 10; tt++) if (tt != 4) {
if (nxt[pos+1][tt] <= dest) nP = max(nP, nxt[pos+1][tt]);
}
tDist+=2;
pos = nP;
}
update(nextE, letdst, idx, tDist);
}
}
// cout << "EXPD" << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
int st = 0;
while (st < n && s[st] == 'e') st++;
int rem = st;
s = s.substr(st);
n = (int)s.size();
memset(dist, 0x3f, sizeof(dist));
for (int j = 0; j < 10; j++) nxt[n][j] = n;
for (int i = n-1; i >= 0; i--) {
for (int j = 0; j < 10; j++) nxt[i][j] = nxt[i+1][j];
nxt[i][s[i]-'a'] = i;
}
for (int i = 0; i < n; i++) if (s[i] == 'e') {
nxtnE[i] = n;
for (int j = 0; j < 10; j++) if (j != 4) {
nxtnE[i] = min(nxtnE[i], nxt[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
jmp[i][j][0] = i;
for (int k = 1; k <= JMPS; k++) {
jmp[i][j][k] = jmp[i][j][k-1];
if (jmp[i][j][k] < n) jmp[i][j][k] = nxt[jmp[i][j][k]+1][j];
}
}
}
int stE = nxt[0][4];
if (stE == n) {
cout << rem << endl;
return 0;
}
int pE = stE;
idxE[pE] = ccE++;
while (pE < n) {
pE = nxt[pE+1][4];
idxE[pE] = ccE++;
}
expand(0, stE, 0);
int ans = 1000000000;
while (!q.empty()) {
pair<int, pair<int, pii> > entry = q.top(); q.pop();
int nextE = entry.second.first;
int let = entry.second.second.first;
int letidx = entry.second.second.second;
int curDist = -entry.first;
// cout << nextE << " " << let << " " << letidx << " " << curDist << endl;
if (dist[nextE][let][letidx] != curDist) continue;
int thisPos = jmp[nextE][let][letidx+1];
// go back and fill up to nextE
int nwNextE = nxt[thisPos+1][4];
int cntEs = idxE[nwNextE] - idxE[nextE];
if (nwNextE == n) {
ans = min(ans, curDist + cntEs + (thisPos-nextE));
}
else {
expand(nxtnE[nextE], nwNextE, curDist + cntEs + (thisPos-nextE));
}
}
cout << ans + rem << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
132 ms |
124152 KB |
Output is correct |
| 2 |
Correct |
119 ms |
124152 KB |
Output is correct |
| 3 |
Correct |
81 ms |
123768 KB |
Output is correct |
| 4 |
Correct |
196 ms |
124912 KB |
Output is correct |
| 5 |
Correct |
211 ms |
125932 KB |
Output is correct |
| 6 |
Correct |
481 ms |
128104 KB |
Output is correct |
| 7 |
Correct |
265 ms |
124916 KB |
Output is correct |
| 8 |
Correct |
64 ms |
122876 KB |
Output is correct |
| 9 |
Correct |
64 ms |
122872 KB |
Output is correct |
| 10 |
Correct |
64 ms |
123004 KB |
Output is correct |
| 11 |
Correct |
64 ms |
122872 KB |
Output is correct |
| 12 |
Correct |
64 ms |
122872 KB |
Output is correct |
| 13 |
Correct |
133 ms |
124232 KB |
Output is correct |
| 14 |
Correct |
126 ms |
124144 KB |
Output is correct |
| 15 |
Correct |
86 ms |
123896 KB |
Output is correct |
| 16 |
Correct |
134 ms |
124024 KB |
Output is correct |
| 17 |
Correct |
219 ms |
125936 KB |
Output is correct |
| 18 |
Correct |
175 ms |
124400 KB |
Output is correct |
| 19 |
Correct |
110 ms |
123928 KB |
Output is correct |
| 20 |
Correct |
132 ms |
124024 KB |
Output is correct |
| 21 |
Correct |
200 ms |
124936 KB |
Output is correct |
| 22 |
Correct |
211 ms |
125808 KB |
Output is correct |
| 23 |
Correct |
120 ms |
124408 KB |
Output is correct |
| 24 |
Correct |
255 ms |
125932 KB |
Output is correct |
| 25 |
Correct |
202 ms |
125932 KB |
Output is correct |
| 26 |
Correct |
289 ms |
125936 KB |
Output is correct |
| 27 |
Correct |
479 ms |
128304 KB |
Output is correct |
| 28 |
Correct |
483 ms |
128104 KB |
Output is correct |
| 29 |
Correct |
273 ms |
125044 KB |
Output is correct |
| 30 |
Correct |
179 ms |
124408 KB |
Output is correct |
| 31 |
Correct |
324 ms |
125936 KB |
Output is correct |
| 32 |
Correct |
245 ms |
125936 KB |
Output is correct |
| 33 |
Correct |
283 ms |
125936 KB |
Output is correct |
| 34 |
Correct |
412 ms |
128132 KB |
Output is correct |
| 35 |
Correct |
337 ms |
125984 KB |
Output is correct |
| 36 |
Correct |
275 ms |
125092 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2097 ms |
140388 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2053 ms |
140384 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2091 ms |
136664 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2081 ms |
140328 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2088 ms |
140400 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2081 ms |
148564 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2092 ms |
140280 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2088 ms |
140288 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2090 ms |
140384 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2092 ms |
136168 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2097 ms |
249464 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2090 ms |
238940 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2099 ms |
241704 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2090 ms |
258524 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2089 ms |
266248 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2099 ms |
243296 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2112 ms |
247312 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2099 ms |
257876 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2097 ms |
256836 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2094 ms |
250176 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2104 ms |
258576 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2096 ms |
266248 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2104 ms |
254248 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2115 ms |
251612 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2113 ms |
257012 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2115 ms |
248016 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2091 ms |
249500 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2114 ms |
241500 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2105 ms |
238812 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2092 ms |
240368 KB |
Time limit exceeded |
