Submission #1253686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253686		antonn	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	182 ms	134904 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename T>
bool assign_min(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool assign_max(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<ll> pr(1, 0), pg(1, 0), py(1, 0);
    vector<ll> posr, posg, posy;
    for (int i = 0; i < n; i++) {
        pr.push_back(pr.back() + (s[i] == 'R'));
        pg.push_back(pg.back() + (s[i] == 'G'));
        py.push_back(py.back() + (s[i] == 'Y'));
        if (s[i] == 'R') {
            posr.push_back(i);
        } else if (s[i] == 'G') {
            posg.push_back(i);
        } else {
            posy.push_back(i);;
        }
    }
    vector<vector<vector<vector<ll>>>> dp(py.back() + 1, vector<vector<vector<ll>>>(pr.back() + 1, vector<vector<ll>>(pg.back() + 1, vector<ll>(3, 2e9))));
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for (int cy = 0; cy <= py.back(); cy++) {
        for (int cr = 0; cr <= pr.back(); cr++) {
            for (int cg = 0; cg <= pg.back(); cg++) {
                for (ll lst = 0; lst < 3; lst++) {
                    if ((lst == 0 && cr == 0) || (lst == 1 && cg == 0) || (lst == 2 && cy == 0)) {
                        continue;
                    }
                    for (int olst = 0; olst < 3; olst++) {
                        if (olst == lst) {
                            continue;
                        }
                        ll add = 0;
                        if (lst == 0) {
                            add = max(0ll, pg[posr[cr - 1]] - cg) + max(0ll, py[posr[cr - 1]] - cy);
                        } else if (lst == 1) {
                            add = max(0ll, pr[posg[cg - 1]] - cr) + max(0ll, py[posg[cg - 1]] - cy);
                        } else if (lst == 2) {
                            add = max(0ll, pr[posy[cy - 1]] - cr) + max(0ll, pg[posy[cy - 1]] - cg);
                        }
                        assign_min(dp[cy][cr][cg][lst], dp[cy - (lst == 2)][cr - (lst == 0)][cg - (lst == 1)][olst] + add);
                    }
                }
            }
        }
    }
    ll ans = min({dp[py.back()][pr.back()][pg.back()][0], dp[py.back()][pr.back()][pg.back()][1], dp[py.back()][pr.back()][pg.back()][2]});
    cout << (ans == 2e9 ? -1 : ans) << "\n";
}

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