제출 #378424

#제출 시각아이디문제언어결과실행 시간메모리
378424YJUVim (BOI13_vim)C++14
50 / 100
2104 ms114524 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]; map<ll,ll> dp[N]; string s; vector<ll> loc; ll n,m; ll f(ll have,ll id){ if(have==m)return 0; if(dp[have].find(id)!=dp[have].end())return dp[have][id]; dp[have][id]=INF; if(id>loc[have]){ ll nhave=lwb(loc.begin(),loc.end(),id)-loc.begin(); dp[have][id]=min(dp[have][id],f(nhave,e[loc[have]])+(id-loc[have])); } REP(j,10){ if(j=='e'-'a'||nxt[id+1][j]==n)continue; dp[have][id]=min(dp[have][id],f(have,nxt[id+1][j])+2); } return dp[have][id]; } 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); } sort(loc.begin(),loc.end()); m=loc.size(); cout<<f(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...