Submission #329558

#	Time	Username	Problem	Language	Result	Execution time	Memory
329558		gs18115	Vim (BOI13_vim)	C++14	100 / 100	58 ms	24812 KiB

vim

#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][10];
int dp1[mx][10];
int dp2[mx][10][10];
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<10;i++)
        nxt[n-1][i]=-1;
    for(int i=n-1;i-->0;)
        for(int j=0;j<10;j++)
            nxt[i][j]=s[i+1]==j?i+1:nxt[i+1][j];
    for(int i=0;i<10;i++)
        dp1[0][i]=2;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            dp2[0][i][j]=nxt[0][i]==-1?inf:2+2+nxt[0][i];
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<10;j++)
            dp1[i][j]=inf;
        for(int j=0;j<10;j++)
            for(int k=0;k<10;k++)
                dp2[i][j][k]=inf;
        { // 1->1
            if(!chk[i])
                for(int j=0;j<10;j++)
                    if(s[i]!=j)
                        app(dp1[i][j],dp1[i-1][j]);
            for(int j=0;j<10;j++)
                app(dp1[i][j],dp1[i-1][s[i]]+2);
        }
        { // 1->2
            for(int j=0;j<10;j++)
                if(nxt[i][j]!=1&&s[i]!=j)
                    for(int k=0;k<10;k++)
                            app(dp2[i][j][k],dp1[i-1][j]+2+nxt[i][j]-i);
            for(int j=0;j<10;j++)
                if(nxt[i][j]!=-1)
                    for(int k=0;k<10;k++)
                        app(dp2[i][j][k],dp1[i-1][s[i]]+2+2+nxt[i][j]-i);
        }
        { // 2->1
            for(int j=0;j<10;j++)
                if(s[i]!=j)
                    app(dp1[i][j],dp2[i-1][s[i]][j]);
            for(int j=0;j<10;j++)
                app(dp1[i][j],dp2[i-1][s[i]][s[i]]+2);
        }
        { // 2->2
            for(int j=0;j<10;j++)
                if(nxt[i][j]!=-1&&s[i]!=j)
                    for(int k=0;k<10;k++)
                        if(s[i]!=k)
                            app(dp2[i][j][k],dp2[i-1][j][k]);
            for(int j=0;j<10;j++)
                if(nxt[i][j]!=-1)
                    for(int k=0;k<10;k++)
                        if(s[i]!=k)
                            app(dp2[i][j][k],dp2[i-1][s[i]][k]+2+nxt[i][j]-i);
            for(int j=0;j<10;j++)
                if(nxt[i][j]!=-1&&s[i]!=j)
                    for(int k=0;k<10;k++)
                        app(dp2[i][j][k],dp2[i-1][j][s[i]]+2);
            for(int j=0;j<10;j++)
                if(nxt[i][j]!=-1)
                    for(int k=0;k<10;k++)
                        app(dp2[i][j][k],dp2[i-1][s[i]][s[i]]+2+2+nxt[i][j]-i);
        }
    }
    cout<<dp1[n-1][9]+2*ce-2<<endl;
    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40