Submission #1231350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231350		inesfi	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	258 ms	172104 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int PARCOULEURSMAXI=202,RED=0,GREEN=1,YELLOW=2,RIEN=3,INFINI=1000*1000;
int nbpots;
vector<int> couleurs;
vector<int> posR,posG,posY;
int memo[PARCOULEURSMAXI][PARCOULEURSMAXI][PARCOULEURSMAXI][4];
vector<int> devantR,devantG,devantY;

int dp(int nbR,int nbG,int nbY,int avant){
    if (memo[nbR][nbG][nbY][avant]!=-1){
        return memo[nbR][nbG][nbY][avant];
    }
    if (nbR+nbG+nbY==nbpots){
        memo[nbR][nbG][nbY][avant]=0;
        return 0;
    }
    int r=INFINI;
    int c=INFINI;
    if (nbR!=posR.size()){
        c=min(c,posR[nbR]);
    }
    if (nbG!=posG.size()){
        c=min(c,posG[nbG]);
    }
    if (nbY!=posY.size()){
        c=min(c,posY[nbY]);
    }
    if (avant!=couleurs[c]){ // pas la meme couleur qu'avant
        if (couleurs[c]==RED){
            r=min(r,dp(nbR+1,nbG,nbY,RED));
        }
        else if (couleurs[c]==GREEN){
            r=min(r,dp(nbR,nbG+1,nbY,GREEN));
        }
        else {
            r=min(r,dp(nbR,nbG,nbY+1,YELLOW));
        }
    }
    int mapos=nbR+nbG+nbY;
    if (avant!=RED and couleurs[c]!=RED and nbR!=posR.size()){
        int autrepos=max(devantR[posR[nbR]],nbR)+max(devantG[posR[nbR]],nbG)+max(devantY[posR[nbR]],nbY);
        r=min(r,dp(nbR+1,nbG,nbY,RED)+autrepos-mapos);
    }
    if (avant!=GREEN and couleurs[c]!=GREEN and nbG!=posG.size()){
        int autrepos=max(devantR[posG[nbG]],nbR)+max(devantG[posG[nbG]],nbG)+max(devantY[posG[nbG]],nbY);
        r=min(r,dp(nbR,nbG+1,nbY,GREEN)+autrepos-mapos);
    }
    if (avant!=YELLOW and couleurs[c]!=YELLOW and nbY!=posY.size()){
        int autrepos=max(devantR[posY[nbY]],nbR)+max(devantG[posY[nbY]],nbG)+max(devantY[posY[nbY]],nbY);
        r=min(r,dp(nbR,nbG,nbY+1,YELLOW)+autrepos-mapos);
    }
    /*if (r!=0){
        cout<<42<<endl;
    }*/
    memo[nbR][nbG][nbY][avant]=r;
    //cout<<"RED "<<nbR<<" GREEN "<<nbG<<" YELLOW "<<nbY<<" avant "<<avant<<" rep "<<r<<endl;
    return r;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbpots;
    for (int i=0;i<nbpots;i++){
        char c;
        cin>>c;
        devantR.push_back(posR.size());
        devantG.push_back(posG.size());
        devantY.push_back(posY.size());
        if (c=='R'){
            couleurs.push_back(RED);
            posR.push_back(i);
        }
        else if (c=='G'){
            couleurs.push_back(GREEN);
            posG.push_back(i);
        }
        else {
            couleurs.push_back(YELLOW);
            posY.push_back(i);
        }
    }
    if (max(posR.size(),max(posG.size(),posY.size()))>(nbpots+1)/2){
        cout<<-1<<endl;
        return 0;
    }
    for (int i=0;i<=posR.size();i++){
        for (int j=0;j<=posG.size();j++){
            for (int k=0;k<=posY.size();k++){
                for (int l=0;l<4;l++){
                    memo[i][j][k][l]=-1;
                }
            }
        }
    }
    cout<<dp(0,0,0,RIEN)<<endl;
    /*for (int i=0;i<=posR.size();i++){
        for (int j=0;j<=posG.size();j++){
            for (int k=0;k<=posY.size();k++){
                for (int l=0;l<4;l++){
                    cout<<memo[i][j][k][l]<<" ";
                }
                cout<<endl;
            }
        }
    }*/
    return 0;
}

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