Submission #1107366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107366		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	501 ms	774696 KiB

joi2019_ho_t3

# include <bits/stdc++.h>
using namespace std;
 
# define ll long long
# define pii pair <int, int>
# define pll pair <ll, ll>
# define nl '\n'
# define sz(x) (int)(x).size()
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x << " = " << x << endl;
 
const int maxn = (int)404;
const ll inf = (ll)1e9 + 0;
const int mod = (int)1e9 + 7;
const bool T = 0;

int n;
string s;
int dp[maxn][maxn][maxn][3];
int pref[3][maxn];
vector <int> g[3];
int d[3];

int f (char c) {
    if (c == 'R') return 0;
    if (c == 'G') return 1;
    if (c == 'Y') return 2;
    assert(0);
    return -1;
}

void op (int &a, int b) {
    a = min(a, b);
}

void ma1n () {
    cin >> n >> s;
    g[0].push_back(0);
    g[1].push_back(0);
    g[2].push_back(0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            pref[j][i + 1] = pref[j][i];
        }
        int x = f(s[i]);
        pref[x][i + 1]++;
        g[x].push_back(i + 1);
    }
    memset(dp, 0x3f, sizeof dp);
    int lim = dp[3][2][1][0];
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    // deb(s);
    // exit(0);
    for (int i = 0; i < n; ++i) {
        for (int x = 0; x <= i; ++x) {
            for (int y = 0; y <= i; ++y) {
                if (x + y > i) continue;
                int z = i - x - y;
                d[0] = x, d[1] = y, d[2] = z;
                bool boo = 1;
                for (int j = 0; j < 3; ++j) {
                    if (d[j] > pref[j][n]) {
                        boo = 0;
                    }
                }
                if (!boo) continue;
                for (int prv = 0; prv < 3; ++prv) {
                    for (int cur = 0; cur < 3; ++cur) {
                        if (prv == cur || d[cur] == pref[cur][n]) continue;
                        // cout << "continue everything" << nl;
                        // continue;
                        int othr = prv ^ cur ^ 3;
                        assert(othr >= 0 && othr < 3 && othr != prv && othr != cur);
                        int id = g[cur][d[cur] + 1];
                        op(dp[i + 1][x + (cur == 0)][y + (cur == 1)][cur], dp[i][x][y][prv] + max(pref[prv][id] - d[prv], 0) + max(pref[othr][id] - d[othr], 0));
                    }
                }

            }
        }
    }
    int ans = lim;
    for (int last = 0; last < 3; ++last) {
        ans = min(ans, dp[n][pref[0][n]][pref[1][n]][last]);
        // cout << pref[0][n] << ' ' << pref[1][n] << ' ' << last << ' ' <<dp[n][pref[0][n]][pref[1][n]][last] << nl;
    }
    // for (int x = 0; x <= n; ++x) {
    //     for (int y = 0; y <= n; ++y) {
    //         if (x + y > n) continue;
    //         for (int last = 0; last < 3; ++last) {
    //             ans = min(ans, dp[n][x][y][last]);
    //             if (dp[n][x][y][last] != lim) {
    //                 cout << x << ' ' << y << ' ' << last << ' ' << dp[n][x][y][last] << nl;
    //             }
    //         }
    //     }
    // }
    cout << (ans == lim ? -1 : ans) << nl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int ttt = 1;
    if (T) cin >> ttt;
    while (ttt--) {
        ma1n();
    }
    return 0;
}

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