제출 #1231346

#제출 시각아이디문제언어결과실행 시간메모리
1231346clemmy14Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
1 ms840 KiB
#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, ' ');
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...