Submission #329554

#TimeUsernameProblemLanguageResultExecution timeMemory
329554gs18115Vim (BOI13_vim)C++14
49.61 / 100
86 ms20716 KiB
#include<iostream> #include<vector> #include<algorithm> #define ep emplace #define eb emplace_back #define fi first #define se second #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef pair<int,int>pi; typedef pair<ll,ll>pl; const int inf=1e9+7; const ll INF=1e18+7; const int mx=70010; inline void app(int&x,int y) { x=min(x,y); return; } int s[mx]; bool chk[mx]; int nxt[mx][9]; int dp1[mx][9]; int dp2[mx][9][9]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; int ce=0; for(int i=0;i<n;i++) { char c; cin>>c; if(c=='e') chk[i-ce]=1,ce++; else s[i-ce]=c<'e'?c-'a':c-'a'-1; } if(ce==0) return cout<<0<<endl,0; n-=ce; for(int i=0;i<9;i++) nxt[n-1][i]=-1; for(int i=n-1;i-->0;) for(int j=0;j<9;j++) nxt[i][j]=s[i+1]==j?i+1:nxt[i+1][j]; for(int i=0;i<9;i++) dp1[0][i]=nxt[0][i]==-1?inf:2; for(int i=0;i<9;i++) for(int j=0;j<9;j++) dp2[0][i][j]=inf; for(int i=1;i<n-1;i++) { for(int j=0;j<9;j++) dp1[i][j]=inf; for(int j=0;j<9;j++) for(int k=0;k<9;k++) dp2[i][j][k]=inf; { // 1->1 if(!chk[i]) for(int j=0;j<9;j++) if(nxt[i][j]!=-1&&s[i]!=j) app(dp1[i][j],dp1[i-1][j]); for(int j=0;j<9;j++) if(nxt[i][j]!=-1) app(dp1[i][j],dp1[i-1][s[i]]+2); } { // 1->2 for(int j=0;j<9;j++) if(nxt[i][j]!=1&&s[i]!=j) for(int k=0;k<9;k++) if(nxt[i][k]!=-1) app(dp2[i][j][k],dp1[i-1][j]+2+nxt[i][j]-i); for(int j=0;j<9;j++) if(nxt[i][j]!=-1) for(int k=0;k<9;k++) if(nxt[i][k]!=-1) app(dp2[i][j][k],dp1[i-1][s[i]]+2+2+nxt[i][j]-i); } { // 2->1 for(int j=0;j<9;j++) if(nxt[i][j]!=-1&&s[i]!=j) app(dp1[i][j],dp2[i-1][s[i]][j]); for(int j=0;j<9;j++) if(nxt[i][j]!=-1) app(dp1[i][j],dp2[i-1][s[i]][s[i]]+2); } { // 2->2 for(int j=0;j<9;j++) if(nxt[i][j]!=-1&&s[i]!=j) for(int k=0;k<9;k++) if(nxt[i][k]!=-1&&s[i]!=k) app(dp2[i][j][k],dp2[i-1][j][k]); for(int j=0;j<9;j++) if(nxt[i][j]!=-1) for(int k=0;k<9;k++) if(nxt[i][k]!=-1&&s[i]!=k) app(dp2[i][j][k],dp2[i-1][s[i]][k]+2+nxt[i][j]-i); for(int j=0;j<9;j++) if(nxt[i][j]!=-1&&s[i]!=j) for(int k=0;k<9;k++) if(nxt[i][k]!=-1) app(dp2[i][j][k],dp2[i-1][j][s[i]]+2); for(int j=0;j<9;j++) if(nxt[i][j]!=-1) for(int k=0;k<9;k++) if(nxt[i][k]!=-1) app(dp2[i][j][k],dp2[i-1][s[i]][s[i]]+2+2+nxt[i][j]-i); } } vector<int>cv; for(int i=0;i<n;i++) if(chk[i]) cv.eb(i); int ans=inf; for(int i=0;i<9;i++) if(nxt[0][i]>=cv.back()) ans=min(ans,2+nxt[0][i]-cv[0]); int j=0; for(int i=0;i<cv.back()-1;i++) { while(cv[j]<=i+1) j++; int nx=cv[j]; int nc=s[i+1]; for(int j=0;j<9;j++) if(nxt[i+1][j]>=cv.back()) app(ans,min(dp1[i][nc],dp2[i][nc][nc])+2+nxt[i+1][j]-nx); for(int j=0;j<9;j++) { if(nxt[i][j]==-1||s[i+1]==j||nxt[i][j]>=cv.back()) continue; int nx2=*upper_bound(all(cv),nxt[i][j]); for(int k=0;k<9;k++) if(nxt[i+1][k]>=cv.back()) app(ans,dp2[i][j][nc]+2+nxt[i+1][k]-nx2); } } cout<<ans+2*ce<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...