Submission #559981

#	Time	Username	Problem	Language	Result	Execution time	Memory
559981		messiuuuuu	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	369 ms	780420 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define task "HOT3"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 4e2 + 5;
const ll INF = 1e8 + 5;

int n, dp[MAXN][MAXN][MAXN][3];
string s;

void Input()
{
    cin >> n >> s;
    s = "," + s;
}

int cnt1[MAXN][3], cnt2[MAXN][3], cnt3[MAXN][3];

void Solve()
{
    int cntr = 0, cntg = 0, cnty = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 'R')
        {
            cntr++;
            cnt1[cntr][1] = cntg;
            cnt1[cntr][2] = cnty;
        }
        if (s[i] == 'G')
        {
            cntg++;
            cnt2[cntg][0] = cntr;
            cnt2[cntg][2] = cnty;
        }
        if (s[i] == 'Y')
        {
            cnty++;
            cnt3[cnty][0] = cntr;
            cnt3[cnty][1] = cntg;
        }
    }

    memset(dp, 44, sizeof(dp));
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int i = 0; i <= cntr; i++)
    {
        for (int j = 0; j <= cntg; j++)
        {
            for (int z = 0; z <= cnty; z++)
            {
                if (i < cntr)
                    dp[i + 1][j][z][0] = min(dp[i + 1][j][z][0], min(dp[i][j][z][1], dp[i][j][z][2]) + abs(cnt1[i + 1][1] - j) + abs(cnt1[i + 1][2] - z));
                if (j < cntg)
                    dp[i][j + 1][z][1] = min(dp[i][j + 1][z][1], min(dp[i][j][z][0], dp[i][j][z][2]) + abs(cnt2[j + 1][0] - i) + abs(cnt2[j + 1][2] - z));
                if (z < cnty)
                    dp[i][j][z + 1][2] = min(dp[i][j][z + 1][2], min(dp[i][j][z][0], dp[i][j][z][1]) + abs(cnt3[z + 1][0] - i) + abs(cnt3[z + 1][1] - j));
            }
        }
    }
    int ans = min(dp[cntr][cntg][cnty][0], min(dp[cntr][cntg][cnty][1], dp[cntr][cntg][cnty][2]));
    ans /= 2;
    cout << (ans < INF ? ans : -1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen(taskname".INP" , "r" , stdin);
    //freopen(taskname".OUT" , "w" , stdout);
    Input();
    Solve();
    return 0;
}

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