Submission #393014

#	Time	Username	Problem	Language	Result	Execution time	Memory
393014		wildturtle	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	131 ms	192816 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define ll int
#define f first
#define sc second
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,idx,idx1,idx2,ans;
ll posa[402],posb[402],posc[402],prea[402],preb[402],prec[402],dp[4][402][402][402];
string s;
int main() {
    cin>>n>>s;
    s="*"+s;
    for(ll i=1;i<=n;i++) {
    	prea[i]=prea[i-1];
    	preb[i]=preb[i-1];
    	prec[i]=prec[i-1];
        if(s[i]=='R') {
            a++;
            posa[a]=i;
            prea[i]=a;
        }
        if(s[i]=='G') {
            b++;
            posb[b]=i;
            preb[i]=b;
        }
        if(s[i]=='Y') {
            c++;
            posc[c]=i;
            prec[i]=c;
        }
        //cout<<prea[i]<<" "<<preb[i]<<" "<<prec[i]<<endl;
    }
    for(ll i=0;i<=a;i++) {
        for(ll j=0;j<=b;j++) {
            for(ll u=0;u<=c;u++) {
                for(ll x=0;x<3;x++) {
                    dp[x][i][j][u]=1e9+10;
                }
            }
        }
    }
    for(ll i=0;i<3;i++)
    dp[i][0][0][0]=0;
    for(ll i=0;i<=a;i++) {
        for(ll j=0;j<=b;j++) {
            for(ll u=0;u<=c;u++) {
                for(ll x=0;x<3;x++) {
                    for(ll y=0;y<3;y++) {
                        if(x==y) continue;
                        if(y==0 && i==a) continue;
                        if(y==1 && j==b) continue;
                        if(y==2 && u==c) continue;
                        k=dp[x][i][j][u];
                        if(y==0) {
                            idx=posa[i+1];
                            idx1=posb[j]; idx2=posc[u];
                            k+=max(f,preb[idx]-preb[idx1]);
                            k+=max(f,prec[idx]-prec[idx2]);
                            dp[y][i+1][j][u]=min(dp[y][i+1][j][u],k);
                            if(dp[y][i+1][j][u]<0) cout<<k<<" ";
                        }
                        if(y==1) {
                            idx=posb[j+1];
                            idx1=posa[i]; idx2=posc[u];
                            k+=max(f,prea[idx]-prea[idx1]);
                            k+=max(f,prec[idx]-prec[idx2]);
                            dp[y][i][j+1][u]=min(dp[y][i][j+1][u],k);
                        }
                        if(y==2) {
                            idx=posc[u+1];
                            idx1=posa[i]; idx2=posb[j];
                            k+=max(f,prea[idx]-prea[idx1]);
                            k+=max(f,preb[idx]-preb[idx2]);
                            dp[y][i][j][u+1]=min(dp[y][i][j][u+1],k);
                        }
                    }
                }
            }
        }
    }

    ans=1e9+10;
    for(ll i=0;i<3;i++) {
        ans=min(ans,dp[i][a][b][c]);
    }
    if(ans==1e9+10) cout<<-1;
    else cout<<ans;
}
/*
5
RRGYY
*/

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