Submission #1308919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308919		wangzhiyi33	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	329 ms	380952 KiB

joi2019_ho_t3

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

const int inf=1e18;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int totr=0,totg=0,toty=0;

    s="."+s;
    vector<int>mana[3];
    for(int q=1;q<=n;q++){
        if(s[q]=='R'){
            totr++;
            mana[0].push_back(q);
        }
        else if(s[q]=='Y'){
            toty++;
            mana[2].push_back(q);
        }
        else{
            totg++;
            mana[1].push_back(q);
        }
    }

    int dp[n+1][totr+1][totg+1][3];
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
    for(int q=1;q<=n;q++){
        for(int r=0;r<=totr;r++){
            for(int g=0;g<=totg;g++){
                dp[q][r][g][0]=inf;dp[q][r][g][1]=inf;dp[q][r][g][2]=inf;
                int y=q-r-g;
                if(y<0 || y>toty)continue;

                // cur=0
                int val=inf;
                if(r>0){
                    val=min(dp[q-1][r-1][g][2],dp[q-1][r-1][g][1]);

                    int pos=mana[0][r-1];
                    // cari yang green lebih dari posisi
                    int brp=lower_bound(mana[1].begin(),mana[1].end(),mana[0][r-1])-mana[1].begin();
                    pos+=max(0LL,g-brp);
                    // cari yellow
                    brp=lower_bound(mana[2].begin(),mana[2].end(),mana[0][r-1])-mana[2].begin();
                    pos+=max(0LL,y-brp);

                    //cout<<pos<<" "<<r<<" "<<g<<" "<<y<<endl;
                    val+=abs(pos-q);
                    dp[q][r][g][0]=min(inf,val);
                   // cout<<dp[q][r][g][0]<<endl;
                }

                // cur=1
                val=inf;
                if(g>0){
                    val=min(dp[q-1][r][g-1][2],dp[q-1][r][g-1][0]);
                    
                    int pos=mana[1][g-1];
                    // cari yang red lebih dari posisi
                    int brp=lower_bound(mana[0].begin(),mana[0].end(),mana[1][g-1])-mana[0].begin();
                    pos+=max(0LL,r-brp);
                    // cari yellow
                    brp=lower_bound(mana[2].begin(),mana[2].end(),mana[1][g-1])-mana[2].begin();
                    pos+=max(0LL,y-brp);

                    val+=abs(pos-q);
                    dp[q][r][g][1]=min(inf,val);
                }

                // cur=2
                val=inf;
                if(y>0){
                    val=min(dp[q-1][r][g][0],dp[q-1][r][g][1]);

                    int pos=mana[2][y-1];
                    // cari yang red lebih dari posisi
                    int brp=lower_bound(mana[0].begin(),mana[0].end(),mana[2][y-1])-mana[0].begin();
                    pos+=max(0LL,r-brp);
                    // cari green
                    brp=lower_bound(mana[1].begin(),mana[1].end(),mana[2][y-1])-mana[1].begin();
                    pos+=max(0LL,g-brp);

                    val+=abs(pos-q);
                    dp[q][r][g][2]=min(inf,val);
                }
            }
        }
    }

    int ans=min({dp[n][totr][totg][0],dp[n][totr][totg][1],dp[n][totr][totg][2]});
    if(ans==inf)ans=-1;
    cout<<ans<<endl;
}

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