Submission #1093433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093433		ortsac	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	466 ms	781304 KiB

joi2019_ho_t3

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 405;
int dp[3][MAXN][MAXN][MAXN];
int antes[3][MAXN][MAXN];
vector<int> l[3];
string ORD = "RGY";
const int INF = 0x3f3f3f3f;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        for (int j = 0; j < 3; j++) {
            if (c == ORD[j]) v[i] = j;
        }
        l[v[i]].push_back(i);
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < ((int)l[i].size()); j++) {
            int p = 0;
            for (int k = 1; k <= n; k++) {
                antes[i][j][k] = antes[i][j][k - 1];
                if ((p <= j) && (l[i][p] == k)) {
                    antes[i][j][k]++;
                    p++;
                }
            }
        }
    }
    vector<int> t(3);
    for (int i = 0; i < 3; i++) {
        t[i] = ((int)l[i].size());
    }
    memset(dp, -1, sizeof dp);
    dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int q1 = 0; q1 <= min(i, t[0]); q1++) {
            for (int q2 = 0; q2 <= min(i - q1, t[1]); q2++) {
                for (int c = 0; c < 3; c++) {
                    int q[3] = {q1, q2, i - q1 - q2};
                    bool flag = 0;
                    for (int x = 0; x < 3; x++) {
                        if (q[x] > t[x]) flag = 1;
                    }
                    if (flag) continue;
                    q[c]--;
                    if (q[c] < 0) continue;
                    int pegar = l[c][q[c]];
                    for (int ant = 0; ant < 3; ant++) {
                        if (ant == c) continue;
                        int val = dp[ant][i - 1][q[0]][q[1]];
                        if (val == -1) continue;
                        int cost = pegar - 1;
                        if (q[0] > 0) cost -= antes[0][q[0] - 1][pegar];
                        if (q[1] > 0) cost -= antes[1][q[1] - 1][pegar];
                        if (q[2] > 0) cost -= antes[2][q[2] - 1][pegar];
                        if (dp[c][i][q1][q2] == -1) dp[c][i][q1][q2] = (val + cost);
                        else dp[c][i][q1][q2] = min(dp[c][i][q1][q2], val + cost);
                    }
                }
            }
        }
    }
    int ans = INF, a = l[0].size(), b = l[1].size();
    for (int i = 0; i < 3; i++) {
        if (dp[i][n][a][b] != -1) ans = min(ans, dp[i][n][a][b]);
    }
    if (ans == INF) cout << "-1\n";
    else cout << ans << "\n";
}

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