oj.uz

답안 #329554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329554 2020-11-21T14:29:18 Z gs18115 Vim (BOI13_vim) C++14
49.6111 / 100
 86 ms 20716 KB 
#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;
}

Subtask #1
23.6111111111 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Incorrect 1 ms 492 KB Output isn't correct
3 Correct 1 ms 492 KB Output is correct
4 Incorrect 1 ms 492 KB Output isn't correct
5 Incorrect 1 ms 492 KB Output isn't correct
6 Incorrect 1 ms 492 KB Output isn't correct
7 Incorrect 1 ms 620 KB Output isn't correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Correct 1 ms 364 KB Output is correct
11 Incorrect 1 ms 364 KB Output isn't correct
12 Correct 1 ms 364 KB Output is correct
13 Incorrect 1 ms 492 KB Output isn't correct
14 Incorrect 1 ms 492 KB Output isn't correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Incorrect 1 ms 492 KB Output isn't correct
20 Correct 1 ms 492 KB Output is correct
21 Incorrect 1 ms 492 KB Output isn't correct
22 Incorrect 1 ms 492 KB Output isn't correct
23 Correct 2 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Incorrect 2 ms 492 KB Output isn't correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Incorrect 1 ms 492 KB Output isn't correct
29 Incorrect 1 ms 492 KB Output isn't correct
30 Correct 1 ms 492 KB Output is correct
31 Incorrect 1 ms 492 KB Output isn't correct
32 Correct 1 ms 492 KB Output is correct
33 Correct 1 ms 492 KB Output is correct
34 Incorrect 2 ms 492 KB Output isn't correct
35 Correct 1 ms 492 KB Output is correct
36 Incorrect 1 ms 492 KB Output isn't correct

Subtask #2
6.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1132 KB Output isn't correct
2 Correct 5 ms 1388 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Incorrect 4 ms 1132 KB Output isn't correct
5 Incorrect 5 ms 1516 KB Output isn't correct
6 Correct 6 ms 1772 KB Output is correct
7 Correct 4 ms 1260 KB Output is correct
8 Correct 4 ms 1260 KB Output is correct
9 Correct 5 ms 1388 KB Output is correct
10 Incorrect 9 ms 1516 KB Output isn't correct

Subtask #3
20.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 74 ms 18156 KB Output isn't correct
2 Correct 61 ms 17516 KB Output is correct
3 Incorrect 68 ms 18304 KB Output isn't correct
4 Incorrect 60 ms 18668 KB Output isn't correct
5 Correct 86 ms 20716 KB Output is correct
6 Incorrect 41 ms 9708 KB Output isn't correct
7 Incorrect 65 ms 15596 KB Output isn't correct
8 Correct 74 ms 18156 KB Output is correct
9 Correct 55 ms 13548 KB Output is correct
10 Correct 54 ms 12908 KB Output is correct
11 Incorrect 61 ms 18668 KB Output isn't correct
12 Correct 85 ms 20716 KB Output is correct
13 Correct 78 ms 20460 KB Output is correct
14 Correct 70 ms 20076 KB Output is correct
15 Incorrect 71 ms 16944 KB Output isn't correct
16 Correct 59 ms 18412 KB Output is correct
17 Incorrect 74 ms 18028 KB Output isn't correct
18 Incorrect 69 ms 18284 KB Output isn't correct
19 Correct 60 ms 17388 KB Output is correct
20 Incorrect 62 ms 14700 KB Output isn't correct