Submission #378432

#TimeUsernameProblemLanguageResultExecution timeMemory
378432YJUVim (BOI13_vim)C++14
51 / 100
2131 ms460412 KiB
#include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,no-stack-protector,Ofast") using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const ll N=7e4+5; const ll INF=(1LL<<60); #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<=n;i++) #define X first #define Y second #define pb push_back #define mp make_pair #define lwb lower_bound ll nxt[N][11],e[N]; unordered_map<ll,ll> dp[N]; string s; vector<ll> loc; ll n,m; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>s; REP(j,10)nxt[n][j]=n; for(int i=n-1;i>=0;i--){ REP(j,10)nxt[i][j]=nxt[i+1][j]; nxt[i][s[i]-'a']=i; e[i]=(s[i+1]=='e'?e[i+1]:i+1); if(s[i]=='e')loc.pb(i); } reverse(loc.begin(),loc.end()); m=loc.size(); REP(i,n)dp[m][i]=0; for(int i=m-1;i>=0;i--){ for(int j=n-1;j>=0;j--){ dp[i][j]=INF; if(s[j]=='e')continue; ll ii=lwb(loc.begin(),loc.end(),j)-loc.begin(); if(j>loc[i])dp[i][j]=min(dp[i][j],dp[ii][e[loc[i]]]+(j-loc[i])); for(int k=0;k<10;k++){ if(k=='e'-'a'||nxt[j+1][k]==n)continue; dp[i][j]=min(dp[i][j],dp[i][nxt[j+1][k]]+2); } } } cout<<dp[0][0]+m<<"\n"; //REP(i,m)REP(j,n)cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...