Submission #1231338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231338		clemmy14	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	0 / 100	1 ms	840 KiB

joi2019_ho_t3

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

int n, rr, yy, gg;
vector<int> r, y, g;
vector<vector<vector<int>>> lR, lY, lG;

void cal(int pR, int pY, int pG, char prev) {
    int pos=pR+pY+pG;
    if(pos == n) {
        if(prev == 'R') lR[pR][pY][pG]=0;
        else if(prev == 'Y') lY[pR][pY][pG]=0;
        else lG[pR][pY][pG]=0;
        return;
    }
    //cout << pos << ' ' << pR << ' ' << pY << ' ' << pG << ' ' << prev << endl;
    if(prev == 'R' || prev == ' ') {
        if(pY != yy) {
            cal(pR, pY+1, pG, 'Y');
            lR[pR][pY][pG]=min(lR[pR][pY][pG], lY[pR][pY+1][pG]+max(y[pY]-pos, 0));
        } 
        if(pG != gg) {
            cal(pR, pY, pG+1, 'G');
            lR[pR][pY][pG]=min(lG[pR][pY][pG], lG[pR][pY][pG+1]+max(g[pG]-pos, 0));
        }
    }
    if(prev == 'Y' || prev == ' ') {
        if(pR != rr) {
            cal(pR+1, pY, pG, 'R');
            lY[pR][pY][pG]=min(lY[pR][pY][pG], lR[pR+1][pY][pG]+max(r[pR]-pos, 0));
        }
        if(pG != gg) {
            cal(pR, pY, pG+1, 'G');
            lY[pR][pY][pG]=min(lY[pR][pY][pG], lG[pR][pY][pG+1]+max(g[pG]-pos, 0));
        }
    }
    if(prev == 'G' || prev == ' ') {
        if(pY != yy) {
            cal(pR, pY+1, pG, 'Y');
            lG[pR][pY][pG]=min(lG[pR][pY][pG], lY[pR][pY+1][pG]+max(y[pY]-pos, 0));
        } 
        if(pR != rr) {
            cal(pR+1, pY, pG, 'R');
            lG[pR][pY][pG]=min(lG[pR][pY][pG], lR[pR+1][pY][pG]+max(r[pR]-pos, 0));
        }
    }
}

signed main() {
    cin >> n;
    string s; cin >> s;
    for(int i=0; i<n; i++) {
        if(s[i] == 'R') r.push_back(i);
        else if(s[i] == 'Y') y.push_back(i);
        else g.push_back(i);
    }
    rr=r.size(); yy=y.size(); gg=g.size();
    if(rr > yy+gg+1 || yy > rr+gg+1 || gg > rr+yy+1) {
        cout << "-1"; return 0;
    }

    lR=lY=lG=vector<vector<vector<int>>>(rr+1, vector<vector<int>>(yy+1, vector<int>(gg+1, 1e5)));
    //cout <<rr << ' ' << yy << ' ' << gg << endl;
    cal(0, 0, 0, ' ');

    cout << min(lR[0][0][0], min(lG[0][0][0], lY[0][0][0]));
    
    return 0;
}

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