Submission #1351059

#TimeUsernameProblemLanguageResultExecution timeMemory
1351059gayGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
42 ms79188 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 1e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<ll>> p(3, vector<ll>(n + 1));
    vector<vector<ll>> t(3);
    for (int i = 0; i < n; i++) {
        p[0][i + 1] = p[0][i], p[1][i + 1] = p[1][i], p[2][i + 1] = p[2][i];
        if (s[i] == 'R') {
            p[0][i + 1]++;
            t[0].push_back(i);
        } else if (s[i] == 'G') {
            p[1][i + 1]++;
            t[1].push_back(i);
        } else {
            p[2][i + 1]++;
            t[2].push_back(i);
        }
    }
    ll n1 = (int) t[0].size(), n2 = (int) t[1].size(), n3 = (int) t[2].size();
    vector<vector<vector<vector<ll>>>> dp(3, vector<vector<vector<ll>>>(n1 + 1, vector<vector<ll>>(n2 + 1, vector<ll>(n3 + 1, INF))));
    if (n1 > 0) {
        dp[0][1][0][0] = 0;
    }
    if (n2 > 0) {
        dp[1][0][1][0] = 0;
    }
    if (n3 > 0) {
        dp[2][0][0][1] = 0;
    }
    for (int i = 0; i <= n1; i++) {
        for (int j = 0; j <= n2; j++) {
            for (int k = 0; k <= n3; k++) {
                if (i + j + k < 2) continue;
                if (i != 0) {
                    ll cnt = max(0ll, j - p[1][t[0][i - 1]]) +
                            max(0ll, k - p[2][t[0][i - 1]]);
                    dp[0][i][j][k] = min(dp[1][i - 1][j][k], dp[2][i - 1][j][k]) + cnt;
                }
                if (j != 0) {
                    ll cnt = max(0ll, i - p[0][t[1][j - 1]]) +
                            max(0ll, k - p[2][t[1][j - 1]]);
                    dp[1][i][j][k] = min(dp[0][i][j - 1][k], dp[2][i][j - 1][k]) + cnt;
                }
                if (k != 0) {
                    ll cnt = max(0ll, i - p[0][t[2][k - 1]]) +
                            max(0ll, j - p[1][t[2][k - 1]]);
                    dp[2][i][j][k] = min(dp[0][i][j][k - 1], dp[1][i][j][k - 1]) + cnt;
                }
            }
        }
    }
    ll ans = min({dp[0][n1][n2][n3], dp[1][n1][n2][n3], dp[2][n1][n2][n3]});
    if (ans >= INF) {
        cout << -1;
    } else {
        cout << ans;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...