Submission #1089464

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

joi2019_ho_t3

#include <bits/stdc++.h>

#define EmirBey ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define int long long

using namespace std;

const int N = 3e5+2;
const int INF = 1e9 + 1;
const int mod = 1e9+7;

int n, pref[3][N], cnt[3], ans = 1e18, dp[405][405][405][3];
vector<int> pos[3];
string s;

void solve() {
    cin >> n >> s;
    int x=0;
    s='2'+s;
    for (auto i : s) {
        if (i == '2') continue;
        x++;
        for (int j = 0; j < 3; j++)pref[j][x] += pref[j][x - 1];
        if (i == 'R') {
            cnt[0]++;
            pos[0].pb(x);
            pref[0][x]++;
        }else if(i == 'G') {
            cnt[2]++;
            pos[2].pb(x);
            pref[2][x]++;
        }else if(i == 'Y') {
            cnt[1]++;
            pos[1].pb(x);
            pref[1][x]++;
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int a = 0; a <= cnt[0]; a++) {
            for (int b = 0; b <= cnt[1]; b++) {
                for (int c = 0; c < 3; c++) dp[i][a][b][c] = 1e18;
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a = 0; a <= cnt[0]; a++) {
            for (int b = 0; b <= cnt[1]; b++) {
                if (a + b > i) continue;
                int c = i - (a + b);
                if (c > cnt[2]) continue;
                for (int last = 0; last < 3; last++) {
                    if (last != 0 && a) {
                        int j = pos[0][a - 1];
                        int adj = max(0ll, b - pref[1][j]) + max(0ll, c - pref[2][j]);
                        int val = max(0ll, j + adj - i);
                        dp[i][a][b][0] = min(dp[i][a][b][0], dp[i - 1][a - 1][b][last] + val);
                    }if (last != 1 && b) {
                        int j = pos[1][b - 1];
                        int adj = max(0ll, a - pref[0][j]) + max(0ll, c - pref[2][j]);
                        int val = max(0ll, j + adj - i);
                        dp[i][a][b][1] = min(dp[i][a][b][1], dp[i - 1][a][b - 1][last] + val);
                    }if (last != 2 && c) {
                        int j = pos[2][c - 1];
                        int adj = max(0ll, b - pref[1][j]) + max(0ll, a - pref[0][j]);
                        int val = max(0ll, j + adj - i);
                        dp[i][a][b][2] = min(dp[i][a][b][2], dp[i - 1][a][b][last] + val);
                    }
                }

                if (i == n)ans = min({ans, dp[i][a][b][0], dp[i][a][b][1], dp[i][a][b][2]});
            }
        }
    }

    if (ans == 1e18) cout << "-1\n";
    else cout << ans << '\n';
}

signed main() {
    EmirBey;
    int tt = 1;
    while (tt--) {
        solve();
    }
}

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