제출 #1338336

#제출 시각아이디문제언어결과실행 시간메모리
1338336cnam9Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
64 ms3668 KiB
#include <iostream>
#include <cstring>

using namespace std;


constexpr int N = 400 + 5;

inline void minimize(int &dest, const int source) {
    dest = min(dest, source);
}

int dp[2][N][N][3];
char s[N];
int cntR[N], cntG[N], cntY[N];
int posR[N], posG[N], posY[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt", "r", stdin);

    int n;
    cin >> n;

    cin >> s;

    cntR[0] = 0; for (int i = 0; i < n; i++) { cntR[i + 1] = cntR[i] + (s[i] == 'R'); }
    cntG[0] = 0; for (int i = 0; i < n; i++) { cntG[i + 1] = cntG[i] + (s[i] == 'G'); }
    cntY[0] = 0; for (int i = 0; i < n; i++) { cntY[i + 1] = cntY[i] + (s[i] == 'Y'); }

    for (int i = 0; i <= n; i++) { posR[cntR[i]] = i; }
    for (int i = 0; i <= n; i++) { posG[cntG[i]] = i; }
    for (int i = 0; i <= n; i++) { posY[cntY[i]] = i; }

    memset(dp[0], 0x3f, sizeof(dp[0]));
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;

    for (int i = 0; i < n; i++) {

        for (int R = 0; R <= min(i + 1, cntR[n]); R++)
            for (int G = 0; G <= min(i + 1 - R, cntG[n]); G++)
                for (int last = 0; last < 3; last++)
                    dp[(i + 1) & 1][R][G][last] = 1e9;

        // memset(dp[(i + 1) & 1], 0x3f, sizeof(dp[0]));

        for (int R = 0; R <= min(i, cntR[n]); R++)
            for (int G = 0; G <= min(i - R, cntG[n]); G++)
                for (int last = 0; last < 3; last++)
        {
            int Y = i - R - G;
            if (last != 0) {
                int cG = max(0, cntG[posG[G]] - cntG[posR[R]]);
                int cY = max(0, cntY[posY[Y]] - cntY[posR[R]]);
                minimize(dp[(i + 1) & 1][R + 1][G][0], dp[i & 1][R][G][last] + cG + cY);
            }
            if (last != 1) {
                int cR = max(0, cntR[posR[R]] - cntR[posG[G]]);
                int cY = max(0, cntY[posY[Y]] - cntY[posG[G]]);
                minimize(dp[(i + 1) & 1][R][G + 1][1], dp[i & 1][R][G][last] + cR + cY);
            }
            if (last != 2) {
                int cR = max(0, cntR[posR[R]] - cntR[posY[Y]]);
                int cG = max(0, cntG[posG[G]] - cntG[posY[Y]]);
                minimize(dp[(i + 1) & 1][ R ][ G ][2], dp[i & 1][R][G][last] + cR + cG);
            }
        }
    }

    int res = min(dp[n & 1][cntR[n]][cntG[n]][0],
              min(dp[n & 1][cntR[n]][cntG[n]][1],
                  dp[n & 1][cntR[n]][cntG[n]][2]));

    cout << (res >= (int)1e9 ? -1 : res);

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...