Submission #1107392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107392		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	243 ms	618136 KiB

joi2019_ho_t3

# include <bits/stdc++.h>

// #pragma optimize("g", on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


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)2e5;
const int mod = (int)1e9 + 7;
const bool T = 0;

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

short 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 (short i = 0; i < n; ++i) {
        for (short j = 0; j < 3; ++j) {
            pref[j][i + 1] = pref[j][i];
        }
        short x = f(s[i]);
        pref[x][i + 1]++;
        g[x].push_back(i + 1);
    }
    for (short i = 0; i <= n; ++i) {
        for (short x = 0; x <= pref[0][n]; ++x) {
            for (short y = 0; y <= pref[1][n]; ++y) {
                for (short k = 0; k < 3; ++k) {
                    dp[i][x][y][k] = inf;
                }
            }
        }
    }
    // 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 (short i = 0; i < n; ++i) {
        for (short x = 0; x <= min(i, pref[0][n]); ++x) {
            for (short y = 0; y <= min((short)(i - x), pref[1][n]); ++y) {
                if (x + y > i) continue;
                short z = i - x - y;
                if (z > pref[2][n]) continue;
                d[0] = x, d[1] = y, d[2] = z;
                for (short prv = 0; prv < 3; ++prv) {
                    for (short cur = 0; cur < 3; ++cur) {
                        if (prv == cur || d[cur] == pref[cur][n]) continue;
                        // cout << "continue everything" << nl;
                        // continue;
                        short othr = prv ^ cur ^ 3;
                        assert(othr >= 0 && othr < 3 && othr != prv && othr != cur);
                        short 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 = inf;
    for (short 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 == inf ? -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: 15 / 15
• Subtask 4: 25 / 25