제출 #127661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
127661		tri	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1014 ms	1048580 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int INF = 5e8;

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"); }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

int main() {
    int N;
    cin >> N;

    string colorStr;
    cin >> colorStr;

    vi color(N + 1);
    for (int i = 1; i <= N; i++) {
        if (colorStr[i - 1] == 'R') {
            color[i] = 0;
        } else if (colorStr[i - 1] == 'G') {
            color[i] = 1;
        } else {
            color[i] = 2;
        }
    }

    int dp[N + 1][3][2 * N + 1][2 * N + 1]; //index, ending color, red delta, green delta, (inferred) yellow delta

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k <= 2 * N; k++) {
                for (int l = 0; l <= 2 * N; l++) {
                    dp[i][j][k][l] = INF;
                }
            }
        }
    }

    dp[0][0][N + 0][N + 0] = 0;
    dp[0][1][N + 0][N + 0] = 0;
    dp[0][2][N + 0][N + 0] = 0;

    int d[3];

    for (int i = 1; i <= N; i++) {
        for (d[0] = -N; d[0] <= N; d[0]++) {
            for (d[1] = -N; d[1] <= N; d[1]++) {
                d[2] = -(d[0] + d[1]);

                int tCost = (abs(d[0]) + abs(d[1]) + abs(d[2])) / 2;

                for (int eC = 0; eC < 3; eC++) {
                    int cBest = INF;
                    d[eC]--;
                    d[color[i]]++;

                    if (abs(d[0]) <= N && abs(d[1]) <= N && abs(d[2]) <= N) {
                        for (int pC = 0; pC < 3; pC++) {
                            if (pC != eC) {
                                cBest = min(cBest, dp[i - 1][pC][N + d[0]][N + d[1]] + tCost);
                            }
                        }
                    }

                    // undo
                    d[eC]++;
                    d[color[i]]--;

                    dp[i][eC][N + d[0]][N + d[1]] = cBest;
                }
            }
        }
    }

//    for (int j = 0; j < 3; j++) {
//        for (int k = 0; k <= 2 * N; k++) {
//            for (int l = 0; l <= 2 * N; l++) {
//                int i = 2;
//                ps(i, j, k - N, l - N, ":", dp[i][j][k][l]);
//            }
//        }
//    }

    int ans = min(dp[N][0][N + 0][N + 0], min(dp[N][1][N + 0][N + 0], dp[N][2][N + 0][N + 0]));
    if (ans >= INF) {
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
}

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