Submission #694053

#	Time	Username	Problem	Language	Result	Execution time	Memory
694053		AJR07	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	70 ms	57164 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define DBGRUN(stmt) stmt
#define DBG1(x) cout << #x << ": " << (x) << endl
#define DBG2(x, y) cout << #x << ": " << (x) << ", " << #y << ": " << (y) << endl
#define DBG3(x, y, z) cout << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << endl
#define DBG4(w, x, y, z) cout << #w << ": " << (w) << ", " << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << endl
#define DBG_ARR(a, e) cout << #a << ": "; for (int i = 0; i < e; i++) cout << a[i] << ' '; cout << endl
#define DBG_ARR2D(a, s1, e1, s2, e2) cout << #a << ": " << endl; for (int i = s1; i < e1; i++) { for (int j = s2; j < e2; j++) cout << a[i][j] << ' '; cout << '\n'; }cout << endl
#define DBG_VEC(v) cout << #v << ": "; for (auto i : v) cout << i << ' '; cout << endl
#define DBG_HERE cout << "reached line: " << __LINE__ << endl
#else
#define DBGRUN(stmt)
#define DBG1(x)
#define DBG2(x, y)
#define DBG3(x, y, z)
#define DBG4(w, x, y, z)
#define DBG_ARR(a, e)
#define DBG_ARR2D(a, s1, e1, s2, e2)
#define DBG_VEC(v)
#define DBG_HERE
#endif
#define int long long
#define f first
#define s second
#define pii pair<int, int>
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a)) 
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); --(a))
#define ALLV(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v)) 
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
template <typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B>& a) { out << "(" << a.first << ", " << a.second << ")"; return out; }
template<typename ...Ts, size_t ...Is> ostream& println_tuple_impl(ostream& os, tuple<Ts...> tuple, index_sequence<Is...>) { static_assert(sizeof...(Is) == sizeof...(Ts), "Indices must have same number of elements as tuple types!"); static_assert(sizeof...(Ts) > 0, "Cannot insert empty tuple into stream."); auto last = sizeof...(Ts) - 1; os << "("; return ((os << get<Is>(tuple) << (Is != last ? ", " : ")\n")), ...); }
template<typename ...Ts> ostream& operator<<(ostream& os, const tuple<Ts...>& tuple) { return println_tuple_impl(os, tuple, index_sequence_for<Ts...>{}); }

int N, R, G, Y;
vector<int> rPos, gPos, yPos;
string S, A;
int precomp[3][3][410];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> S;
    FOR(i, 0, N) {
        if (S[i] == 'R') {
            R++;
            rPos.push_back(i);
        }
        if (S[i] == 'G') {
            G++;
            gPos.push_back(i);
        }
        if (S[i] == 'Y') {
            Y++;
            yPos.push_back(i);
        }
    }


    // R
    int beforeG = 0, beforeY = 0;
    FOR(i, 0, rPos.size()) {
        while (beforeG < gPos.size() && gPos[beforeG] <= rPos[i]) beforeG++;
        while (beforeY < yPos.size() && yPos[beforeY] <= rPos[i]) beforeY++;
        precomp[0][0][i] = beforeG;
        precomp[0][1][i] = beforeY;
        // DBG3(i, precomp[0][0][i], precomp[0][1][i]);
    }

    // G
    int beforeR = 0;
    beforeY = 0;
    FOR(i, 0, gPos.size()) {
        while (beforeR < rPos.size() && rPos[beforeR] <= gPos[i]) beforeR++;
        while (beforeY < yPos.size() && yPos[beforeY] <= gPos[i]) beforeY++;
        precomp[1][0][i] = beforeR;
        precomp[1][1][i] = beforeY;
        // DBG3(i, precomp[1][0][i], precomp[1][1][i]);
    }

    // Y
    beforeG = 0, beforeR = 0;
    FOR(i, 0, yPos.size()) {
        while (beforeG < gPos.size() && gPos[beforeG] <= yPos[i]) beforeG++;
        while (beforeR < rPos.size() && rPos[beforeR] <= yPos[i]) beforeR++;
        precomp[2][0][i] = beforeR;
        precomp[2][1][i] = beforeG;
        // DBG3(i, precomp[2][0][i], precomp[2][1][i]);
    }


    int memo[R + 1][G + 1][Y + 1][3];
    memset(memo, -1, sizeof memo);
    FOR(i, 0, 3) memo[0][0][0][i] = 0;

    FORN(RR, 0, R) {
        FORN(GG, 0, G) {
            FORN(YY, 0, Y) {
                FOR(lastUsed, 0, 3) {
                    if (memo[RR][GG][YY][lastUsed] == -1) continue;
                    if (RR < R && lastUsed != 0) {
                        int ad = 0;
                        ad += max(GG - (precomp[0][0][RR]), 0ll);
                        ad += max(YY - (precomp[0][1][RR]), 0ll);
                        if (memo[RR + 1][GG][YY][0] == -1)
                            memo[RR + 1][GG][YY][0] = ad + memo[RR][GG][YY][lastUsed];
                        else
                            memo[RR + 1][GG][YY][0] = min(memo[RR + 1][GG][YY][0], ad + memo[RR][GG][YY][lastUsed]);
                        // DBG4(RR + 1, GG, YY, memo[RR + 1][GG][YY][0]);
                    }
                    if (GG < G && lastUsed != 1) {
                        int ad = 0;
                        ad += max(RR - (precomp[1][0][GG]), 0ll);
                        ad += max(YY - (precomp[1][1][GG]), 0ll);
                        if (memo[RR][GG + 1][YY][1] == -1)
                            memo[RR][GG + 1][YY][1] = ad + memo[RR][GG][YY][lastUsed];
                        else
                            memo[RR][GG + 1][YY][1] = min(memo[RR][GG + 1][YY][1], ad + memo[RR][GG][YY][lastUsed]);
                        // DBG4(RR, GG + 1, YY, memo[RR][GG + 1][YY][1]);
                    }

                    if (YY < Y && lastUsed != 2) {
                        int ad = 0;
                        ad += max(RR - (precomp[2][0][YY]), 0ll);
                        ad += max(GG - (precomp[2][1][YY]), 0ll);
                        if (memo[RR][GG][YY + 1][2] == -1)
                            memo[RR][GG][YY + 1][2] = ad + memo[RR][GG][YY][lastUsed];
                        else
                            memo[RR][GG][YY + 1][2] = min(memo[RR][GG][YY + 1][2], ad + memo[RR][GG][YY][lastUsed]);
                        // DBG4(RR, GG, YY + 1, memo[RR][GG][YY + 1][2]);
                    }
                }
            }
        }
    }

    int res = 1e18;
    FOR(i, 0, 3) {
        if (memo[R][G][Y][i] != -1) res = min(res, memo[R][G][Y][i]);
    }
    if (res == 1e18) cout << -1;
    else cout << res;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:28:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
joi2019_ho_t3.cpp:51:5: note: in expansion of macro 'FOR'
   51 |     FOR(i, 0, N) {
      |     ^~~
joi2019_ho_t3.cpp:28:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
joi2019_ho_t3.cpp:69:5: note: in expansion of macro 'FOR'
   69 |     FOR(i, 0, rPos.size()) {
      |     ^~~
joi2019_ho_t3.cpp:28:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                                         ~~~~^~~~~
joi2019_ho_t3.cpp:69:5: note: in expansion of macro 'FOR'
   69 |     FOR(i, 0, rPos.size()) {
      |     ^~~
joi2019_ho_t3.cpp:70:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         while (beforeG < gPos.size() && gPos[beforeG] <= rPos[i]) beforeG++;
      |                ~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:71:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while (beforeY < yPos.size() && yPos[beforeY] <= rPos[i]) beforeY++;
      |                ~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:28:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
joi2019_ho_t3.cpp:80:5: note: in expansion of macro 'FOR'
   80 |     FOR(i, 0, gPos.size()) {
      |     ^~~
joi2019_ho_t3.cpp:28:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                                         ~~~~^~~~~
joi2019_ho_t3.cpp:80:5: note: in expansion of macro 'FOR'
   80 |     FOR(i, 0, gPos.size()) {
      |     ^~~
joi2019_ho_t3.cpp:81:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while (beforeR < rPos.size() && rPos[beforeR] <= gPos[i]) beforeR++;
      |                ~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:82:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while (beforeY < yPos.size() && yPos[beforeY] <= gPos[i]) beforeY++;
      |                ~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:28:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
joi2019_ho_t3.cpp:90:5: note: in expansion of macro 'FOR'
   90 |     FOR(i, 0, yPos.size()) {
      |     ^~~
joi2019_ho_t3.cpp:28:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                                         ~~~~^~~~~
joi2019_ho_t3.cpp:90:5: note: in expansion of macro 'FOR'
   90 |     FOR(i, 0, yPos.size()) {
      |     ^~~
joi2019_ho_t3.cpp:91:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         while (beforeG < gPos.size() && gPos[beforeG] <= yPos[i]) beforeG++;
      |                ~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:92:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         while (beforeR < rPos.size() && rPos[beforeR] <= yPos[i]) beforeR++;
      |                ~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:28:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
joi2019_ho_t3.cpp:101:5: note: in expansion of macro 'FOR'
  101 |     FOR(i, 0, 3) memo[0][0][0][i] = 0;
      |     ^~~
joi2019_ho_t3.cpp:29:31: warning: unnecessary parentheses in declaration of 'RR' [-Wparentheses]
   29 | #define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
      |                               ^
joi2019_ho_t3.cpp:103:5: note: in expansion of macro 'FORN'
  103 |     FORN(RR, 0, R) {
      |     ^~~~
joi2019_ho_t3.cpp:29:31: warning: unnecessary parentheses in declaration of 'GG' [-Wparentheses]
   29 | #define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
      |                               ^
joi2019_ho_t3.cpp:104:9: note: in expansion of macro 'FORN'
  104 |         FORN(GG, 0, G) {
      |         ^~~~
joi2019_ho_t3.cpp:29:31: warning: unnecessary parentheses in declaration of 'YY' [-Wparentheses]
   29 | #define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
      |                               ^
joi2019_ho_t3.cpp:105:13: note: in expansion of macro 'FORN'
  105 |             FORN(YY, 0, Y) {
      |             ^~~~
joi2019_ho_t3.cpp:28:30: warning: unnecessary parentheses in declaration of 'lastUsed' [-Wparentheses]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
joi2019_ho_t3.cpp:106:17: note: in expansion of macro 'FOR'
  106 |                 FOR(lastUsed, 0, 3) {
      |                 ^~~
joi2019_ho_t3.cpp:28:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
joi2019_ho_t3.cpp:145:5: note: in expansion of macro 'FOR'
  145 |     FOR(i, 0, 3) {
      |     ^~~

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