Submission #1275374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275374		MisterReaper	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	191 ms	134840 KiB

joi2019_ho_t3

// File gvif3.cpp created on 02.10.2025 at 11:20:37
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int inf = int(1E9);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::string S;
    std::cin >> S;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'R') {
            A[i] = 0;
        } else if (S[i] == 'G') {
            A[i] = 1;
        } else {
            A[i] = 2;
        }
    }

    std::vector<std::vector<int>> ids(3);
    std::vector<std::vector<int>> pre(3, std::vector<int>(N + 1));
    for (int i = 0; i < N; ++i) {
        ids[A[i]].emplace_back(i);
        pre[0][i + 1] = pre[0][i] + (A[i] == 0);
        pre[1][i + 1] = pre[1][i] + (A[i] == 1);
        pre[2][i + 1] = pre[2][i] + (A[i] == 2);
    }

    int R = pre[0][N];
    int G = pre[1][N];
    int B = pre[2][N];

    std::vector f(R + 1,  std::vector(G + 1, std::vector(B + 1, std::vector<int>(3, inf))));
    f[0][0][0][0] = 0;
    f[0][0][0][1] = 0;
    f[0][0][0][2] = 0;

    for (int i = 0; i <= R; ++i) {
        for (int j = 0; j <= G; ++j) {
            for (int k = 0; k <= B; ++k) {
                for (int x = 0; x < 3; ++x) {
                    for (int y = 0; y < 3; ++y) {
                        if (x == y) {
                            continue;
                        }
                        int ni = i + (y == 0);
                        int nj = j + (y == 1);
                        int nk = k + (y == 2);
                        if (ni > R || nj > G || nk > B) {
                            continue;
                        }
                        int id = ids[y][(y == 0 ? i : (y == 1 ? j : k))];
                        chmin(f[ni][nj][nk][y], f[i][j][k][x] + std::max(0, pre[0][id] - i) + std::max(0, pre[1][id] - j) + std::max(0, pre[2][id] - k));
                    }
                }
            }
        }
    }

    int ans = std::min({f[R][G][B][0], f[R][G][B][1], f[R][G][B][2]});
    if (ans == inf) {
        ans = -1;
    }
    
    std::cout << ans << '\n';

    return 0;
}

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