Submission #1093392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093392		ortsac	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	1 ms	444 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define fr first
#define se second

const int INF = 0x3f3f3f3f;

string blz = "RGY";
vector<int> s[3];
int val[3];

int32_t main() {
    //freopen("in", "r", stdin);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'R') v[i] = 0;
        else if (c == 'G') v[i] = 1;
        else v[i] = 2;
    }
    // calc first batch
    for (int i = 0; i < 3; i++) {
        val[i] = INF;
        vector<int> x = v;
        for (int j = 0; j < n; j++) {
            if (v[j] == i) {
                x.erase(x.begin() + j);
                x.insert(x.begin(), i);
                val[i] = j;
                s[i] = x;
                break;
            }
        }
    }
    // calc all next ones
    for (int k = 1; k < n; k++) {
        vector<int> nVal(3, INF);
        vector<vector<int>> nS(3);
        for (int i = 0; i < 3; i++) {
            if (val[i] == INF) continue;
            for (int l = 0; l < 3; l++) {
                if (l == i) continue;
                vector<int> x = s[i];
                for (int j = k; j < n; j++) {
                    if (x[j] == l) {
                        int np = (val[i] + (j - k));
                        if (np < nVal[l]) {
                            x.erase(x.begin() + j);
                            x.insert(x.begin() + k, l);
                            nS[l] = x;
                            nVal[l] = np;
                        }
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < 3; i++) {
            val[i] = nVal[i];
            s[i] = nS[i];
        }
    }
    // print ans
    int ans = min(val[0], min(val[1], val[2]));
    if (ans == INF) cout << "-1\n";
    else cout << ans << "\n";
}

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