Submission #1351144

#TimeUsernameProblemLanguageResultExecution timeMemory
1351144guardianecGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
125 ms173048 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    string s;
    cin >> s;
    vector<ll> pos[3];
    ll cnt[3][407];
    for (int i=0; i<3; i++) cnt[i][0] = 0;

    for (int i=0; i<n; i++) {
        ll idx = -1;
        if (s[i]=='R') idx = 0;
        else if (s[i]=='G') idx = 1;
        else if (s[i]=='Y') idx = 2;

        pos[idx].push_back(i);
        for (int j=0; j<3; j++) {
            cnt[j][i+1] = cnt[j][i]+(j==idx);
        }
    }

    ll n1 = pos[0].size();
    ll n2 = pos[1].size();
    ll n3 = pos[2].size();

    vector<vector<vector<vector<ll>>>> dp(n1+1, vector<vector<vector<ll>>>(n2+1, vector<vector<ll>>(n3+1, vector<ll>(4, 1e9))));
    dp[0][0][0][3] = 0;
    for (int r=0; r<=n1; r++) {
        for (int g=0; g<=n2; g++) {
            for (int y=0; y<=n3; y++) {
                for (int i=0; i<4; i++) {
                    ll curr = dp[r][g][y][i];
                    if (curr==1e9) continue;

                    if (r<n1 && i!=0) {
                        ll p = pos[0][r];
                        ll c = max(0LL, cnt[1][p]-g)+max(0LL, cnt[2][p]-y);
                        dp[r+1][g][y][0] = min(dp[r+1][g][y][0], curr+c);
                    }

                    if (g<n2 && i!=1) {
                        ll p = pos[1][g];
                        ll c = max(0LL, cnt[0][p]-r)+max(0LL, cnt[2][p]-y);
                        dp[r][g+1][y][1] = min(dp[r][g+1][y][1], curr+c);
                    }

                    if (y<n3 && i!=2) {
                        ll p = pos[2][y];
                        ll c = max(0LL, cnt[0][p]-r)+max(0LL, cnt[1][p]-g);
                        dp[r][g][y+1][2] = min(dp[r][g][y+1][2], curr+c);
                    }
                }
            }
        }
    }

    ll res = 1e9;
    for (int i=0; i<3; i++) res = min(res, dp[n1][n2][n3][i]);

    if (res==1e9) cout << -1;
    else cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...