oj.uz

Submission #127669

# Submission time Handle Problem Language Result Execution time Memory
127669 2019-07-09T21:20:07 Z tri Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 19216 KB 
#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 pre[3][1000][1000]; //index, ending color, red delta, green delta, (inferred) yellow delta
int nxt[3][1000][1000];

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;
        }
    }

//    ps("read", N);
//
//    ps("allocate");

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

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

    int d[3];
//    ps("init");

    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, pre[pC][N + d[0]][N + d[1]] + tCost);
                            }
                        }
                    }

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

                    nxt[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++) {
                    pre[j][k][l] = nxt[j][k][l];
                    nxt[j][k][l] = INF;
                }
            }
        }
    }

//    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(pre[0][N + 0][N + 0], min(pre[1][N + 0][N + 0], pre[2][N + 0][N + 0]));
    if (ans >= INF) {
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Correct 4 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 4 ms 1148 KB Output is correct
11 Incorrect 3 ms 1016 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Correct 4 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 4 ms 1148 KB Output is correct
11 Incorrect 3 ms 1016 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Execution timed out 1080 ms 19216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Correct 4 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 4 ms 1148 KB Output is correct
11 Incorrect 3 ms 1016 KB Output isn't correct
12 Halted 0 ms 0 KB -