제출 #375990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375990		valerikk	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	446 ms	792196 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 407;
const int INF = 0x3f3f3f3f;

int dp[N][N][N][3];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<int> r, g, y;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'R')
            r.push_back(i);
        if (s[i] == 'G')
            g.push_back(i);
        if (s[i] == 'Y')
            y.push_back(i);
    }
    int red = r.size(), green = g.size(), yellow = y.size();
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < 3; ++i)
        dp[0][0][0][i] = 0;
    for (int i = 0; i <= red; ++i) {
        for (int j = 0; j <= green; ++j) {
            for (int k = 0; k <= yellow; ++k) {
                for (int last = 0; last < 3; ++last) {
                    int pos = i + j + k;
                    int val = dp[i][j][k][last];
                    if (val == INF)
                        continue;
                    if (i < red && last != 0) dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], val + abs(pos - r[i]));
                    if (j < green && last != 1) dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], val + abs(pos - g[j]));
                    if (k < yellow && last != 2) dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], val + abs(pos - y[k]));
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < 3; ++i)
        ans = min(ans, dp[red][green][yellow][i]);
    if (ans == INF) {
        cout << -1 << endl;
        return 0;
    }
    cout << ans / 2 << endl;
    return 0;
}

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