Submission #378102

#	Time	Username	Problem	Language	Result	Execution time	Memory
378102		smjleo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	107 ms	164972 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1000000007, mod2 = 998244353;

// change this
const int N = 405;

int n, si[3], arr[N], dp[N][N][N][3], pf[3][N];

vector<int> pos[3];

int sum(int i, int x, int y) {
    // (x, y]
    if (x > y) return 0;
    return pf[i][y] - pf[i][x];
}

signed main() {
    io;
    cin >> n;
    for (int i=0; i<3; i++) pos[i].push_back(0);
    for (int i=1; i<=n; i++) {
        char c;
        cin >> c;
        if (c == 'R') arr[i] = 0;
        else if (c == 'G') arr[i] = 1;
        else arr[i] = 2;

        si[arr[i]]++; pf[arr[i]][i]++;
        pos[arr[i]].push_back(i);

        for (int j=0; j<3; j++) pf[j][i] += pf[j][i-1];
    }

    for (int i=0; i<=si[0]; i++) {
        for (int j=0; j<=si[1]; j++) {
            for (int k=0; k<=si[2]; k++) {
                for (int tak=0; tak<3; tak++) {
                    if (!(i+j+k)) continue;
                    // i: R, j: G, k: Y, tak: which one to take
                    dp[i][j][k][tak] = 1e9;

                    for (int prev=0; prev<3; prev++) {
                        // what was the previous one?
                        if (prev == tak) continue;  // collision
                        if (tak == 0) {
                            if (!i) break;
                            dp[i][j][k][tak] = min(dp[i][j][k][tak], 
                                dp[i-1][j][k][prev]
                                + sum(1, pos[1][j], pos[0][i]) 
                                + sum(2, pos[2][k], pos[0][i])
                            );
                        } else if (tak == 1) {
                            if (!j) break;
                            dp[i][j][k][tak] = min(dp[i][j][k][tak],
                                dp[i][j-1][k][prev]
                                + sum(0, pos[0][i], pos[1][j])
                                + sum(2, pos[2][k], pos[1][j])
                            );
                        } else {
                            if (!k) break;
                            dp[i][j][k][tak] = min(dp[i][j][k][tak],
                                dp[i][j][k-1][prev]
                                + sum(0, pos[0][i], pos[2][k])
                                + sum(1, pos[1][j], pos[2][k])
                            );
                        }
                    }
                }
            }
        }
    }

    int ans = 1e9;
    for (int i=0; i<3; i++) ans = min(ans, dp[si[0]][si[1]][si[2]][i]);

    cout << (ans >= 1e9 ? -1 : ans) << nl;
}

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