Submission #1231372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231372		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;
    int newPR=(pR == rr ? -1 : r[pR]), newPY=(pY == yy ? -1 : y[pY]), newPG=(pG == gg ? -1 : g[pG]);
    for(int i=0; i<pR; i++) {
        if(pY != yy && r[i] > y[pY]) newPY++;
        if(pG != gg && r[i] > g[pG]) newPG++;
    }
    for(int i=0; i<pY; i++) {
        if(pR != rr && y[i] > r[pR]) newPR++;
        if(pG != gg && y[i] > g[pG]) newPG++;
    }
    for(int i=0; i<pG; i++) {
        if(pY != yy && g[i] > y[pY]) newPY++;
        if(pR != rr && g[i] > r[pR]) newPR++;
    }

    //cout << newPR << ' ' << newPY << ' ' << newPG << endl;
    //return;

    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(newPY-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(newPG-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(newPR-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(newPG-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(newPY-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(newPR-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)));

    cal(0, 0, 0, ' ');
    int ans = min(lR[0][0][0], min(lG[0][0][0], lY[0][0][0]));
    if(ans == 1e5) ans=-1;
    cout << ans;
    return 0;
}

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