Submission #1188423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188423		M_W_13	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	386 ms	755400 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
const int MAXN = 401;
int INF = 1e9;
int dp[MAXN][MAXN][MAXN][3];
int jakie[MAXN][3][3];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int T[n];
    string s;
    cin >> s;
    vector<int> p[3];
    rep(c, 3) {
        p[c].pb(-1);
    }
    rep(i, n) {
        if (s[i] == 'R') {
            T[i] = 0;
        }
        else if (s[i] == 'G') {
            T[i] = 1;
        }
        else {
            T[i] = 2;
        }
        p[T[i]].pb(i);
    }
    int sz[3];
    rep(c, 3) {
        sz[c] = p[c].size();
    }
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    int iter[3];
    rep(c, 3) {
        iter[c] = 0;
        rep(d, 3) {
            jakie[0][c][d] = 0;
        }
    }
    rep(i, n) {
        iter[T[i]]++;
        rep(c, 3) {
            jakie[iter[T[i]]][T[i]][c] = iter[c];
        }
    }
    rep(i, n) {
        rep(j, n) {
            rep(k, n) {
                rep(c, 3) {
                    dp[i][j][k][c] = INF;
                }
            }
        }
    }
    rep(c, 3) {
        dp[0][0][0][c] = 0;
    }
    rep(i, n) {
        rep(j, n) {
            rep(k, n) {
                if ((i + j + k) == 0) {
                    continue;
                }
                if (i >= sz[0] || j >= sz[1] || k >= sz[2]) {
                    continue;
                }
                rep(c, 3) {
                    if (c == 0) {
                        if (i > 0) {
                            dp[i][j][k][c] = max(0, j - jakie[i][c][1]) + max(0, k - jakie[i][c][2]) + min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]);
                        }
                    }
                    else if (c == 1) {
                        if (j > 0) {
                            dp[i][j][k][c] = max(0, i - jakie[j][c][0]) + max(0, k - jakie[j][c][2]) + min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]);
                        }
                    }
                    else {
                        if (k > 0) {
                            dp[i][j][k][c] = max(0, i - jakie[k][c][0]) + max(0, j - jakie[k][c][1]) + min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]);
                        }
                    }
                    // cout << "i = " << i << " j = " << j << " k = " << k << " c = " << c << " dp = " << dp[i][j][k][c] << '\n';
                }
            }
        }
    }
    int ans = INF;
    rep(c, 3) {
        ans = min(ans, dp[sz[0] - 1][sz[1] - 1][sz[2] - 1][c]);
    }
    if (ans >= INF) {
        cout << -1 << '\n';
        return 0;
    }
    cout << ans << '\n';
	return 0;
}

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