Submission #1181019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181019		iamhereforfun	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	81 ms	194376 KiB

joi2019_ho_t3

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(S) ((S) & -(S))

const int N = 4e2 + 5;
const int M = 4e5 + 5;
const int Q = 1e5 + 5;
const int LG = 20;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int B = 350;

int n, c0, c1, c2, dp[3][N][N][N], num[3][N], ans = 1e9;
vector<int> pos[3];
string s;

void solve()
{
    cin >> n >> s;
    c1 = c2 = c0 = 0;
    pos[0].push_back(-1);
    pos[1].push_back(-1);
    pos[2].push_back(-1);
    for (int x = 1; x <= n; x++)
    {
        if (s[x - 1] == 'R')
        {
            pos[0].push_back(x);
            c0++;
        }
        if (s[x - 1] == 'G')
        {
            pos[1].push_back(x);
            c1++;
        }
        if (s[x - 1] == 'Y')
        {
            pos[2].push_back(x);
            c2++;
        }
        num[0][x] = pos[0].size();
        num[1][x] = pos[1].size();
        num[2][x] = pos[2].size();
    }
    // cout << pos[0].size() << " " << c0 << "\n";
    // return;
    for (int x = 0; x <= c0; x++)
    {
        for (int y = 0; y <= c1; y++)
        {
            for (int z = 0; z <= c2; z++)
            {
                if (x + y + z == 0)
                {
                    dp[0][0][0][0] = 0;
                    dp[1][0][0][0] = 0;
                    dp[2][0][0][0] = 0;
                    continue;
                }
                dp[0][x][y][z] = INF;
                dp[1][x][y][z] = INF;
                dp[2][x][y][z] = INF;
                if (x > 0)
                {
                    dp[0][x][y][z] = min(dp[1][x - 1][y][z], dp[2][x - 1][y][z]) + pos[0][x] - x - y - z;
                    dp[0][x][y][z] += max(0, -num[1][pos[0][x]] + num[1][pos[1][y]]);
                    dp[0][x][y][z] += max(0, -num[2][pos[0][x]] + num[2][pos[2][z]]);
                }
                if (y > 0)
                {
                    dp[1][x][y][z] = min(dp[0][x][y - 1][z], dp[2][x][y - 1][z]) + pos[1][y] - x - y - z;
                    dp[1][x][y][z] += max(0, -num[0][pos[1][y]] + num[0][pos[0][x]]);
                    dp[1][x][y][z] += max(0, -num[2][pos[1][y]] + num[2][pos[2][z]]);
                }
                if (z > 0)
                {
                    dp[2][x][y][z] = min(dp[0][x][y][z - 1], dp[1][x][y][z - 1]) + pos[2][z] - x - y - z;
                    dp[2][x][y][z] += max(0, -num[0][pos[2][z]] + num[0][pos[0][x]]);
                    dp[2][x][y][z] += max(0, -num[1][pos[2][z]] + num[1][pos[1][y]]);
                }
                if(x + y + z == n) ans = min(dp[0][x][y][z], min(dp[1][x][y][z], dp[2][x][y][z]));
            }
        }
    }
    if(ans >= INF) cout << -1;
    else cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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