Submission #952869

#	Time	Username	Problem	Language	Result	Execution time	Memory
952869		offlineDeletionTrickFan	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	375 ms	774996 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 404;
int dp[MAXN][MAXN][MAXN][3], pos[3][MAXN], v[MAXN], cnt[3], pref[3][MAXN];
signed main() {
    int n;
    string s;
    cin >> n >> s;
    memset(dp, '?', sizeof dp), memset(pos, 0, sizeof pos), memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i) {
        v[i] = s[i - 1] == 'R' ? 0 : s[i - 1] == 'G' ? 1 : 2;
        pref[0][i] = pref[0][i - 1] + (v[i] == 0);
        pref[1][i] = pref[1][i - 1] + (v[i] == 1);
        pref[2][i] = pref[2][i - 1] + (v[i] == 2);
        pos[v[i]][++cnt[v[i]]] = i;
    }
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int red = 0; red <= cnt[0]; ++red) {
        for (int green = 0; green <= cnt[1]; ++green) {
            for (int blue = 0; blue <= cnt[2]; ++blue) {
                if (red) dp[red][green][blue][0] = min(dp[red - 1][green][blue][1], dp[red - 1][green][blue][2]) + max(0, pref[1][pos[0][red]] - green) + max(0, pref[2][pos[0][red]] - blue);
                if (green) dp[red][green][blue][1] = min(dp[red][green - 1][blue][0], dp[red][green - 1][blue][2]) + max(0, pref[0][pos[1][green]] - red) + max(0, pref[2][pos[1][green]] - blue);
                if (blue) dp[red][green][blue][2] = min(dp[red][green][blue - 1][0], dp[red][green][blue - 1][1]) + max(0, pref[0][pos[2][blue]] - red) + max(0, pref[1][pos[2][blue]] - green);
            }
        }
    }
    int ans = *min_element(dp[cnt[0]][cnt[1]][cnt[2]], dp[cnt[0]][cnt[1]][cnt[2]] + 3);
    if (ans > n * n) cout << -1;
    else cout << ans;
}

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