Submission #243062

#TimeUsernameProblemLanguageResultExecution timeMemory
243062ffaoVim (BOI13_vim)C++14
12.50 / 100
2096 ms71840 KiB
#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; int ccE; int nxt[71000][11]; int idxE[71000]; int jmp[71000][11][11]; int dist[71000][11][11]; 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 && nxt[nextE][letdst] != n) { int dest = nxt[nextE][letdst]; 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, 0, 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++) { for (int j = 0; j < 10; j++) { jmp[i][j][0] = i; for (int k = 1; k <= 10; 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(nextE, nwNextE, curDist + cntEs + (thisPos-nextE)); } // go forward for (int j = 0; j < 10; j++) if (j != 4) { int np = nxt[thisPos+1][j]; if (np == n) continue; int nIdx = -1; for (int k = 1; k <= 10; k++) { if (jmp[nextE][j][k] == np) nIdx = k-1; } if (nIdx != -1) update(nextE, j, nIdx, curDist + 2); } } cout << ans + rem << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...