Submission #1306436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306436		chithanhnguyen	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	97 ms	194404 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

const int MAXN = 405;
const int INF  = 1e9 + 7;
int n, cnt[MAXN], pos[3][MAXN], pref[3][MAXN];
int dp[3][MAXN][MAXN][MAXN];
string s;

void init() {
    cin >> n >> s;
    s = ' ' + s;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 2; ++j) pref[j][i] = pref[j][i - 1];

        char c = s[i];
        if (c == 'R') {
            cnt[0]++;
            pos[0][cnt[0]] = i;
            pref[0][i]++;
        } else if (c == 'G') {
            cnt[1]++;
            pos[1][cnt[1]] = i;
            pref[1][i]++;
        } else {
            cnt[2]++;
            pos[2][cnt[2]] = i;
            pref[2][i]++;
        }
    }
}

void solve() {
    for (int i = 0; i <= 2; ++i)
        for (int r = 0; r <= cnt[0]; ++r)
            for (int g = 0; g <= cnt[1]; ++g)
                for (int y = 0; y <= cnt[2]; ++y) {
                    if (!r && !g && !y) dp[i][r][g][y] = 0;
                    else dp[i][r][g][y] = INF;
                }
    
    for (int r = 0; r <= cnt[0]; ++r) {
        for (int g = 0; g <= cnt[1]; ++g) {
            for (int y = 0; y <= cnt[2]; ++y) {
                for (int cur = 0; cur <= 2; ++cur) {
                    for (int nxt = 0; nxt <= 2; ++nxt) {
                        if (cur == nxt) continue;
                        if (nxt == 0 && r == cnt[0]) continue;
                        if (nxt == 1 && g == cnt[1]) continue;
                        if (nxt == 2 && y == cnt[2]) continue;

                        // cout << "State " << cur << " (" << r << ", " << g << ", " << y << ") -> ";
                        // cout << nxt;
                        // cout << '\n';
                        int nr = r, ng = g, ny = y;
                        int cost = 0;

                        if (nxt == 0) {
                            nr = r + 1;
                            int p = pos[0][r + 1]; 
                            // for (int i = 1; i <= ng; ++i) 
                            //     if (pos[1][i] > p) ++cost;
                            // for (int i = 1; i <= ny; ++i) 
                            //     if (pos[2][i] > p) ++cost;
                            cost += max(0, pref[1][pos[1][ng]] - pref[1][p]);
                            cost += max(0, pref[2][pos[2][ny]] - pref[2][p]);
                        } else if (nxt == 1) {
                            ng = g + 1;
                            int p = pos[1][g + 1]; 
                            // for (int i = 1; i <= nr; ++i) 
                            //     if (pos[0][i] > p) ++cost;
                            // for (int i = 1; i <= ny; ++i) 
                            //     if (pos[2][i] > p) ++cost;
                            cost += max(0, pref[0][pos[0][nr]] - pref[0][p]);
                            cost += max(0, pref[2][pos[2][ny]] - pref[2][p]);
                        } else {
                            ny = y + 1;
                            int p = pos[2][y + 1]; 
                            // for (int i = 1; i <= nr; ++i) 
                            //     if (pos[0][i] > p) ++cost;
                            // for (int i = 1; i <= ng; ++i) 
                            //     if (pos[1][i] > p) ++cost;
                            cost += max(0, pref[0][pos[0][nr]] - pref[0][p]);
                            cost += max(0, pref[1][pos[1][ng]] - pref[1][p]);
                        }

                        dp[nxt][nr][ng][ny] = min(dp[nxt][nr][ng][ny], dp[cur][r][g][y] + cost);
                    }
                }
            }
        }
    }

    int res = INF;
    for (int i = 0; i <= 2; ++i)
        res = min(res, dp[i][cnt[0]][cnt[1]][cnt[2]]);
    cout << (res == INF ? -1 : res);
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    solve();

    return 0;
}

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