Submission #481426

#TimeUsernameProblemLanguageResultExecution timeMemory
481426LoboGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
60 / 100
491 ms1048580 KiB
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 450

ii n, dp[maxn][maxn][maxn][4];
ii qtd1, qtd2, qtd3;
ii pos1[maxn], pos2[maxn], pos3[maxn];
ii cnt1[maxn], cnt2[maxn], cnt3[maxn];
string s;

ii sol(ii c1, ii c2, ii c3, ii ant) {
    if(dp[c1][c2][c3][ant] != -1) return dp[c1][c2][c3][ant];

    ii ans = INFii;

    if(c1 != qtd1 && ant != 1) {
        ans = min(ans, sol(c1+1,c2,c3,1) + max(0,cnt2[pos2[c2]]-cnt2[pos1[c1+1]]) + max(0,cnt3[pos3[c3]]-cnt3[pos1[c1+1]]));
    }

    if(c2 != qtd2 && ant != 2) {
        ans = min(ans, sol(c1,c2+1,c3,2) + max(0,cnt1[pos1[c1]]-cnt1[pos2[c2+1]]) + max(0,cnt3[pos3[c3]]-cnt3[pos2[c2+1]]));
    }

    if(c3 != qtd3 && ant != 3) {
        ans = min(ans, sol(c1,c2,c3+1,3) + max(0,cnt2[pos2[c2]]-cnt2[pos3[c3+1]]) + max(0,cnt1[pos1[c1]]-cnt1[pos3[c3+1]]));
    }

    return dp[c1][c2][c3][ant] = ans;
}

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

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> s;

    for(ii i = 1; i <= n; i++) {
        cnt1[i] = cnt1[i-1];
        cnt2[i] = cnt2[i-1];
        cnt3[i] = cnt3[i-1];

        if(s[i-1] == 'R') {
            cnt1[i]++;
            pos1[++qtd1] = i;
        }
        if(s[i-1] == 'G') {
            cnt2[i]++;
            pos2[++qtd2] = i;
        }
        if(s[i-1] == 'Y') {
            cnt3[i]++;
            pos3[++qtd3] = i;
        }
    }

    for(ii i = 0; i <= n; i++) {
        for(ii j = 0; j <= n; j++) {
            for(ii k = 0; k <= n; k++) {
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = dp[i][j][k][3] = -1;
            }
        }
    }

    if(qtd1 > (n+1)/2 || qtd2 > (n+1)/2 || qtd3 > (n+1)/2) {
        cout << -1 << endl;
        return 0;
    }
    
    dp[qtd1][qtd2][qtd3][0] = dp[qtd1][qtd2][qtd3][1] = dp[qtd1][qtd2][qtd3][2] = dp[qtd1][qtd2][qtd3][3]  = 0;
    cout << sol(0,0,0,0) << endl;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...