제출 #491285

#제출 시각아이디문제언어결과실행 시간메모리
491285AdamGSVim (BOI13_vim)C++14
16.67 / 100
568 ms180304 KiB
#include<bits/stdc++.h> using namespace std; #define rep(a, b) for(int a = 0; a < (b); ++a) #define pb push_back #define st first #define nd second const int LIM=7e4+7, INF=1e9+7; vector<pair<int,int>>S[LIM]; vector<pair<pair<int,int>,int>>V[LIM][10]; int kiedy[10], nxt[LIM][10], ostatni[LIM], odl[LIM][10]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, lst=-1; string s; cin >> n >> s; rep(i, n) { if(s[i]=='e') { s[i]='a'; lst=i; } else if(s[i]=='a') s[i]='e'; } rep(i, 10) kiedy[i]=INF; for(int i=n-1; i>=0; --i) { rep(j, 10) nxt[i][j]=kiedy[j]; for(int j=1; j<10; ++j) if(kiedy[j]<INF) { S[kiedy[j]].pb({i, 2}); } if(i<n-1) S[i].pb({i+1, 1}); kiedy[s[i]-'a']=i; ostatni[i]=INF; } priority_queue<pair<int,pair<int,int>>>q; q.push({0, {lst, 0}}); while(!q.empty()) { int o=-q.top().st, p=q.top().nd.st; q.pop(); if(ostatni[p]<=o) continue; ostatni[p]=o; for(auto i : S[p]) if(ostatni[i.st]>o+i.nd) { q.push({-o-i.nd, {i.st, 0}}); } } rep(i, n) { for(int j=1; j<10; ++j) if(nxt[i][j]<INF) { if(nxt[i][0]>nxt[i][j]) { V[i][0].pb({{nxt[i][j], 0}, 2}); } else { int c=j, mi=INF; for(int z=1; z<10; ++z) mi=min(mi, nxt[nxt[i][0]][z]); if(mi==nxt[i][j]) c=0; V[i][0].pb({{mi, c}, 2+nxt[i][j]-nxt[i][0]}); } } for(int j=1; j<10; ++j) if(nxt[i][j]<INF) { for(int l=1; l<10; ++l) if(nxt[i][l]<INF) { int p=nxt[i][j]; if(nxt[p][0]>nxt[i][l]) { V[i][j].pb({{nxt[i][l], 0}, 2}); } else { int c=l, mi=INF; for(int z=1; z<10; ++z) mi=min(mi, nxt[p][z]); if(mi==nxt[i][l]) c=0; V[i][j].pb({{mi, c}, 2+nxt[i][l]-nxt[p][0]}); } } } } int ans=INF; rep(i, n) rep(j, 10) odl[i][j]=INF; 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(odl[a][b]<=o) continue; odl[a][b]=o; int p=nxt[a][b]; if(!b) p=a; if(nxt[p][0]==INF) { ans=min(ans, o); } else { ans=min(ans, o+ostatni[a]+lst-nxt[p][0]); } for(auto i : V[a][b]) if(odl[i.st.st][i.st.nd]>o+i.nd) { q.push({-o-i.nd, {i.st.st, i.st.nd}}); } } rep(i, n) if(s[i]=='a') ++ans; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...