Submission #1184860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184860		jerzyk	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	87 ms	178248 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 100'000'000;
const ll M = 1'000'000'007LL;
const int N = 403;
int dp[N][N][N][3], il[N][3], pos[N][3];
int tp[200];

void Solve()
{
    tp['R'] = 0; tp['G'] = 1; tp['Y'] = 2;
    int n;
    string s;
    cin >> n >> s;
    s = '#' + s;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
            for(int r = 0; r <= 2; ++r) dp[0][i][j][r] = II;
    for(int r = 0; r <= 2; ++r) dp[0][0][0][r] = 0;
    for(int l = 1; l <= n; ++l)
    {
        int a = tp[(int)s[l]];
        for(int r = 0; r <= 2; ++r) il[l][r] = il[l - 1][r];
        ++il[l][a];
        pos[il[l][a]][a] = l;
    }
    for(int l = 1; l <= n; ++l)
    {
        for(int i = 0; i <= l; ++i)
            for(int j = 0; j <= l - i; ++j)
            {
                int k = l - i - j;
                if(i > il[n][0] || j > il[n][1] || k > il[n][2]) continue;
                for(int r = 0; r <= 2; ++r)
                    dp[l][i][j][r] = II;
                int p = pos[i][0];
                if(i > 0)
                    dp[l][i][j][0] = min(dp[l - 1][i - 1][j][1], dp[l - 1][i - 1][j][2]) + p + max(0, j - il[p][1]) + max(0, k - il[p][2]) - l;
                p = pos[j][1];
                if(j > 0)
                    dp[l][i][j][1] = min(dp[l - 1][i][j - 1][0], dp[l - 1][i][j - 1][2]) + p + max(0, i - il[p][0]) + max(0, k - il[p][2]) - l;
                p = pos[k][2];
                if(k > 0)
                    dp[l][i][j][2] = min(dp[l - 1][i][j][0], dp[l - 1][i][j][1]) + p + max(0, j - il[p][1]) + max(0, i - il[p][0]) - l;
                //cerr << l << " " << pos[i][0] << " " << dp[l][i][j][0] << " | " << j << " " << pos[j][1] << " " << dp[l][i][j][1] << " | " << k << " " << pos[k][2] << " " << dp[l][i][j][2] << "\n";
            }
    }
    int answer = II;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n - i; ++j)
        {
            int k = n - i - j;
            if(i > il[n][0] || j > il[n][1] || k > il[n][2]) continue;
            for(int r = 0; r <= 2; ++r)
                answer = min(answer, dp[n][i][j][r]);
        }
    if(answer < II)
        cout << answer << "\n";
    else
        cout << -1 << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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