Submission #531986

#	Time	Username	Problem	Language	Result	Execution time	Memory
531986		syl123456	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	196 ms	4284 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1, typename ...T2>
void debug(bool _split, T1 i, T2 ...j) {
    if (_split)
        cerr << ", ";
    cerr << i;
    debug(true, j...);
}
#define debug(args...) cout << "Line" << __LINE__ << " : [" << #args << << "] is [" << debug(false, args) << "]" << endl;

typedef pair<int, int> pi;
typedef long long ll;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    const int N = 405;
    int n;
    string s;
    cin >> n >> s;
    int cnt[3];
    cnt[0] = count(all(s), 'R');
    cnt[1] = count(all(s), 'G');
    cnt[2] = count(all(s), 'Y');
    vector<int> pos[3];
    int pre[n][3];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j)
            pre[i][j] = i ? pre[i - 1][j] : 0;
        if (s[i] == 'R')
            pos[0].push_back(i), ++pre[i][0];
        else if (s[i] == 'G')
            pos[1].push_back(i), ++pre[i][1];
        else
            pos[2].push_back(i), ++pre[i][2];
    }
    int dp[2][N][N][3];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < 3; ++k)
                dp[0][i][j][k] = inf;
    for (int i = 0; i < 3; ++i)
        dp[0][0][0][i] = 0;
    for (int _i = 0; _i <= cnt[0]; ++_i) {
        int x = _i & 1, y = !x, i[3];
        i[0] = _i;
        for (i[1] = 0; i[1] < N; ++i[1])
            for (i[2] = 0; i[2] < N; ++i[2])
                for (int j = 0; j < 3; ++j)
                    dp[y][i[1]][i[2]][j] = inf;
        for (i[1] = 0; i[1] <= cnt[1]; ++i[1])
            for (i[2] = 0; i[2] <= cnt[2]; ++i[2])
                for (int j = 0; j < 3; ++j)
                    for (int k = 0; k < 3; ++k)
                        if (j != k && i[k] < cnt[k]) {
                            int tmp = dp[x][i[1]][i[2]][j];
                            ++i[k], y = i[0] & 1;
                            for (int l = 0; l < 3; ++l)
                                tmp += max(0, i[l] - pre[pos[k][i[k] - 1]][l]);
                            dp[y][i[1]][i[2]][k] = min(dp[y][i[1]][i[2]][k], tmp);
                            --i[k];
                        }
    }
    int ans = inf;
    for (int i = 0; i < 3; ++i)
        ans = min(ans, dp[cnt[0] & 1][cnt[1]][cnt[2]][i]);
    cout << (ans < inf ? ans : -1);
}

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