Submission #1183383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183383		alterio	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	20 / 100	74 ms	163812 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 402;

int dp[mxn][mxn][mxn][3], sum[mxn][3], pos[mxn][3], cnt[3];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = "." + s;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'R') pos[++cnt[0]][0] = i;
        if (s[i] == 'G') pos[++cnt[1]][1] = i;
        if (s[i] == 'Y') pos[++cnt[2]][2] = i;
        for (int j = 0; j < 3; j++) sum[i][j] = cnt[j];
    }
    for (int j = 0; j < 3; j++) dp[0][0][0][j] = 0;
    for (int i = 1; i <= n; i++) {
        for (int r = 0; r <= min(i, cnt[0]); r++) {
            for (int g = 0; g + r <= i && g <= cnt[1]; g++) {
                int y = i - (r + g);
                if (y > cnt[2]) continue;
                if (r) dp[i][r][g][0] = min(dp[i - 1][r - 1][g][1], dp[i - 1][r - 1][g][2]) + max(0, g - sum[pos[r][0]][1]) + max(0, y - sum[pos[r][0]][2]);
                else dp[i][r][g][0] = 1e9;
                if (g) dp[i][r][g][1] = min(dp[i - 1][r][g - 1][0], dp[i - 1][r][g - 1][2]) + max(0, r - sum[pos[g][1]][0]) + max(0, y - sum[pos[g][1]][2]);
                else dp[i][r][g][1] = 1e9;
                if (y) dp[i][r][g][2] = min(dp[i - 1][r][g][0], dp[i - 1][r][g][1]) + max(0, r - sum[pos[y][2]][0] + max(0, g - sum[pos[y][2]][1]));
                else dp[i][r][g][2] = 1e9;
            }
        }
    }
    int ans = 1e9;
    for (int j = 0; j < 3; j++) ans = min(ans, dp[n][cnt[0]][cnt[1]][j]);
    cout << (ans == 1e9 ? -1 : ans);
}

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