Submission #122187

#TimeUsernameProblemLanguageResultExecution timeMemory
122187Adhyyan1252Vim (BOI13_vim)C++11
27.78 / 100
50 ms15488 KiB
#include<bits/stdc++.h> using namespace std; #define INF 1e7 int main(){ int n; cin>>n; vector<int> a(n+2); for(int i = 1; i <= n; i++){ char c; cin>>c; a[i] = c - 'a'; } vector<vector<int> > next(n+2, vector<int>(10, INF)); for(int i = n; i > 0; i--){ next[i] = next[i+1]; next[i][a[i]] = i; } vector<vector<int> > pref(n+2, vector<int>(10, 0)); for(int i = 1; i <= n; i++){ pref[i] = pref[i-1]; pref[i][a[i]]++; } vector<vector<int> > dp(n+2, vector<int>(10, INF)); for(int i = 0; i < 10; i++){ dp[n+1][i] = 0; } for(int i = n; i > 0; i--){ for(int j = 0; j < 10; j++){ int cur = next[i][j]; //cursor is here. need to delete all from i to n if(cur == INF) continue; //first come back to the leftest e if(j == 4){ continue; } int indx = next[i][4]; if(indx == INF){ //no e's after i dp[i][j] = 0; }else if(indx > cur){ //this section has no e's so just move forward by exactly one fk for(int k = 0; k < 10; k++){ if(k == 4) continue; dp[i][j] = min(dp[i][j], 2 + dp[cur+1][k]); //cursor moves to next[cur+1][k] } }else if(next[cur+1][4] == INF){ int cost = cur - indx + pref[cur][4] - pref[indx-1][4]; dp[i][j] = cost; }else{ //first go left to reach leftest e. int cost = cur - indx + pref[cur][4] - pref[indx-1][4]; //jump from indx+1 to next[cur+1][k] //find next element, after int after = cur; for(int k = 0; k < 10; k++){ if(k == 4) continue; after = min(after, next[indx][k]); } int oc = INF; for(int k = 0; k < 10; k++){ if(k == 4) continue; if(next[cur+1][k] == INF) continue; oc = min(oc, dp[cur+1][k] + 2*(pref[next[cur+1][k]][k] - pref[after][k])); } dp[i][j] = min((int)INF, oc + cost); } } // cout<<"DP "<<i<<" : "; // for(int j = 0; j < 10; j++){ // cout<<dp[i][j]<<"\t"; // } // cout<<endl; } int ans = dp[1][a[1]]; // for(int i = 0; i < 10; i++){ // ans = min(ans, dp[1][i]); // } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...