Submission #930960

#	Time	Username	Problem	Language	Result	Execution time	Memory
930960		WongYiKai	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	198 ms	327764 KiB

joi2019_ho_t3

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

ll visited[405][405][405][3];
ll dp[405][405][405][3];
ll tr,tg,ty,tt;
ll rr[405],gg[405],yy[405],r2[405],g2[405],y2[405];

ll dp2(ll r,ll g,ll y,ll last){
    if (visited[r][g][y][last]==1) return dp[r][g][y][last];
    visited[r][g][y][last] = 1;
    if (r+g+y==1){
        return 0;
    }
    ll ind,temp;
    ll ar=r,ag=g,ay=y;
    if (last==0){
        ind = rr[tr-r+1];
        temp = abs(r+g+y-1-ind+max(tg-g-g2[ind],0)+max(ty-y-y2[ind],0));
        ar--;
    }
    else if (last==1){
        ind = gg[tg-g+1];
        temp = abs(r+g+y-1-ind+max(tr-r-r2[ind],0)+max(ty-y-y2[ind],0));
        ag--;
    }
    else{
        ind = yy[ty-y+1];
        temp = abs(r+g+y-1-ind+max(tg-g-g2[ind],0)+max(tr-r-r2[ind],0));
        ay--;
    }
    ll ans1=1000000,ans2=1000000,ans3=1000000;
    if (ar>0 && last!=0) ans1 = dp2(ar,ag,ay,0)+temp;
    if (ag>0 && last!=1) ans2 = dp2(ar,ag,ay,1)+temp;
    if (ay>0 && last!=2) ans3 = dp2(ar,ag,ay,2)+temp;
    ll ans = min(min(ans1,ans2),ans3);
    dp[r][g][y][last] = ans;
    // cout << r << " " << g << " " << y << " " << last << " " << ans << " " << ind << "\n";
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t;
    t=1;
    while (t--){
        ll n;
        cin >> n;
        string s;
        cin >> s;
        ll r1=1,g1=1,y1=1;
        rr[0] = n,gg[0]=n,yy[0]=n;
        for (int i=n-1;i>=0;i--){
            if (s[i]=='R') {
                rr[r1] = i;
                r1++;
            }
            else if (s[i]=='G') {
                gg[g1] = i;
                g1++;
            }
            else {
                yy[y1] = i;
                y1++;
            }
            r2[i] = r1-1;
            g2[i] = g1-1;
            y2[i] = y1-1;
        }
        tr = r1-1;
        ty = y1-1;
        tg = g1-1;
        tt = n;
        ll ans1=1000000,ans2=1000000,ans3=1000000;
        if (tr>0) ans1 = dp2(tr,tg,ty,0);
        if (tg>0) ans2 = dp2(tr,tg,ty,1);
        if (ty>0) ans3 = dp2(tr,tg,ty,2);
        ll ans = min(min(ans1,ans2),ans3);
        if (ans<500000) cout << ans;
        else cout << -1;
        // dp2(0,1,1,1);
    }
}

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