Submission #1339941

#TimeUsernameProblemLanguageResultExecution timeMemory
1339941hoangtien69Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
78 ms162980 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 405;
const int INF = 1e9;

int n;
string s;
int dp[MAXN][MAXN][MAXN][3];
int pre0[MAXN];
int pre1[MAXN];
int pre2[MAXN];
int pos0[MAXN];
int pos1[MAXN];
int pos2[MAXN];
int cnt0 = 0;
int cnt1 = 0;
int cnt2 = 0;

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

    cin >> n;
    cin >> s;
    s = "*" + s;
    for (int i = 1; i <= n; i++)
    {
        pre0[i] = pre0[i - 1];
        pre1[i] = pre1[i - 1];
        pre2[i] = pre2[i - 1];
        if (s[i] == 'R')
        {
            pre0[i]++;
            cnt0++;
            pos0[cnt0] = i;
        }
        else if (s[i] == 'G')
        {
            pre1[i]++;
            cnt1++;
            pos1[cnt1] = i;
        }
        else if (s[i] == 'Y')
        {
            pre2[i]++;
            cnt2++;
            pos2[cnt2] = i;
        }
    }
    for (int i = 0; i <= cnt0; i++)
    {
        for (int j = 0; j <= cnt1; j++)
        {
            for (int k = 0; k <= cnt2; k++)
            {
                for (int l = 0; l <= 2; l++)
                {
                    dp[i][j][k][l] = INF;
                }
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int i = 0; i <= cnt0; i++)
    {
        for (int j = 0; j <= cnt1; j++)
        {
            for (int k = 0; k <= cnt2; k++)
            {
                if (i + 1 <= cnt0)
                {
                    int cost0 = max(0, pre1[pos0[i + 1]] - j) + max(0, pre2[pos0[i + 1]] - k);
                    dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], min(dp[i][j][k][1], dp[i][j][k][2]) + cost0);
                }
                if (j + 1 <= cnt1)
                {
                    int cost1 = max(0, pre0[pos1[j + 1]] - i) + max(0, pre2[pos1[j + 1]] - k);
                    dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], min(dp[i][j][k][0], dp[i][j][k][2]) + cost1);
                }
                if (k + 1 <= cnt2)
                {
                    int cost2 = max(0, pre0[pos2[k + 1]] - i) + max(0, pre1[pos2[k + 1]] - j);
                    dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], min(dp[i][j][k][0], dp[i][j][k][1]) + cost2);
                }
            }
        }
    }
    int ans = INF;
    for (int l = 0; l <= 2; l++)
    {
        ans = min(ans, dp[cnt0][cnt1][cnt2][l]);
    }
    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...