Submission #591278

#	Time	Username	Problem	Language	Result	Execution time	Memory
591278		piOOE	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	280 ms	354992 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int N = 401;

int dp[3][N][N][N];
array<int, 3> pl[N][N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string S;
    cin >> S;
    vector<int> a(n);
    array<int, 3> cnt{};
    vector<vector<int>> g(3);
    for (int i = 0; i < n; ++i) {
        a[i] = S[i] == 'R' ? 0 : S[i] == 'G' ? 1 : 2;
        ++cnt[a[i]];
        g[a[i]].push_back(i);
    }
    if (max({cnt[0], cnt[1], cnt[2]}) > (n + 1) / 2) {
        cout << -1;
        return 0;
    }
    pl[0][0][0] = {-1, -1, -1};
    for (int t = 0; t < 3; ++t) {
        reverse(g[t].begin(), g[t].end());
    }
    for (int sum = 1; sum <= n; ++sum) {
        for (int f = 0; f <= cnt[0]; ++f) {
            for (int s = 0; s <= cnt[1]; ++s) {
                if (f + s > sum) {
                    break;
                }
                int t = sum - f - s;
                if (t > cnt[2]) {
                    continue;
                }
                array<int, 3> temp = {f == 0 ? n + 1 : g[0][f - 1], s == 0 ? n + 1 : g[1][s - 1],
                                      t == 0 ? n + 1 : g[2][t - 1]};
                int idx = min_element(temp.begin(), temp.end()) - temp.begin();
                if (idx == 0) {
                    pl[f][s][t] = pl[f - 1][s][t];
                } else if (idx == 1) {
                    pl[f][s][t] = pl[f][s - 1][t];
                } else {
                    pl[f][s][t] = pl[f][s][t - 1];
                }
                for (int k = 0; k < 3; ++k) if (pl[f][s][t][k] != -1) pl[f][s][t][k] += 1;
                pl[f][s][t][idx] = 0;
                array<int, 3> num = {f, s, t};
                if (sum != n) {
                    array<int, 3> k = pl[f][s][t];
                    for (int p = 0; p < 3; ++p) {
                        dp[p][f][s][t] = 1000'000'000;
                        for (int nxt = 0; nxt < 3; ++nxt) {
                            if (p == nxt || num[nxt] == 0) {
                                continue;
                            }
                            int ans = dp[nxt][f - (nxt == 0)][s - (nxt == 1)][t - (nxt == 2)] + pl[f][s][t][nxt];
                            if (dp[p][f][s][t] > ans) {
                                dp[p][f][s][t] = ans;
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 1000'000'000;
    int f = cnt[0], s = cnt[1], t = cnt[2];
    array<int, 3> k = pl[f][s][t];
    for (int nxt = 0; nxt < 3; ++nxt) {
        if (cnt[nxt] == 0) {
            continue;
        }
        int val = dp[nxt][f - (nxt == 0)][s - (nxt == 1)][t - (nxt == 2)] + pl[f][s][t][nxt];
        ans = min(ans, val);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:57:35: warning: variable 'k' set but not used [-Wunused-but-set-variable]
   57 |                     array<int, 3> k = pl[f][s][t];
      |                                   ^
joi2019_ho_t3.cpp:76:19: warning: variable 'k' set but not used [-Wunused-but-set-variable]
   76 |     array<int, 3> k = pl[f][s][t];
      |                   ^

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