Submission #1165709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165709		AlgorithmWarrior	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	57 ms	4276 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=405;
int dp[MAX][MAX][3][2];
int v[MAX];
int poz[3][MAX];
int pref[MAX][3];
int n;
char trans[300];
int freq[3];
int delta[][2]={{-1,0},
              {0,-1},
              {0,0}};
int fr[3];

void read(){
    cin>>n;
    trans['R']=0;
    trans['G']=1;
    trans['Y']=2;
    int i,j;
    for(i=1;i<=n;++i){
        char ch;
        cin>>ch;
        v[i]=trans[(int)ch];
        poz[v[i]][++freq[v[i]]]=i;
        pref[i][v[i]]=1;
        for(j=0;j<3;++j)
            pref[i][j]+=pref[i-1][j];
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int get_dp(){
    int ult,i,penult;
    for(fr[0]=0;fr[0]<MAX;++fr[0])
        for(fr[1]=0;fr[1]<MAX;++fr[1])
            for(ult=0;ult<3;++ult)
                for(i=0;i<2;++i)
                    dp[fr[0]][fr[1]][ult][i]=INF;
    if(freq[0]) dp[1][0][0][1]=poz[0][1]-1;
    if(freq[1]) dp[0][1][1][1]=poz[1][1]-1;
    if(freq[2]) dp[0][0][2][1]=poz[2][1]-1;
    for(i=2;i<=n;++i)
        for(fr[0]=0;fr[0]<=freq[0];++fr[0])
            for(fr[1]=0;fr[1]<=freq[1];++fr[1])
                if(fr[0]+fr[1]<=i && i-fr[0]-fr[1]<=freq[2]){
                    fr[2]=i-fr[0]-fr[1];
                    for(ult=0;ult<3;++ult){
                        if(!fr[ult]) continue;
                        dp[fr[0]][fr[1]][ult][i&1]=INF;
                        int add=0;
                        int pos=poz[ult][fr[ult]];
                        for(penult=0;penult<3;++penult)
                            if(penult!=ult && fr[penult]<pref[pos][penult])
                                add+=pref[pos][penult]-fr[penult];
                        for(penult=0;penult<3;++penult)
                            if(penult!=ult)
                                minself(dp[fr[0]][fr[1]][ult][i&1],dp[fr[0]+delta[ult][0]][fr[1]+delta[ult][1]][penult][!(i&1)]+add);
                    }
                }
    int ans=INF;
    for(ult=0;ult<3;++ult)
        minself(ans,dp[freq[0]][freq[1]][ult][n&1]);
    return (ans<INF)?ans:-1;
}

int main()
{
    read();
    cout<<get_dp();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25