oj.uz

Submission #693281

# Submission time Handle Problem Language Result Execution time Memory
693281 2023-02-02T15:13:39 Z nianny Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
75 / 100
 500 ms 125808 KB 
    #include <bits/stdc++.h>
    using namespace std;

// #define DEBUG

    #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;
    map<tuple<int, int, int, int>, int> memo;
    vector<int> rPos, gPos, yPos;
    string S, A;
     
    int dp(int RR, int GG, int YY, int lastUsed) {
        if (memo.find({ RR, GG, YY, lastUsed }) != memo.end())
            return memo[{RR, GG, YY, lastUsed}];
        if (RR == R && GG == G && YY == Y) return 0;
        int res = 1e18, idx = RR + GG + YY;
     
        if (RR < R && lastUsed != 0) {
            int nearestR = rPos[RR], ad = 0;
            // if (idx >= nearestR) {
                ad += max(GG - (upper_bound(gPos.begin(), gPos.end(), nearestR) - gPos.begin()), 0ll);
                ad += max(YY - (upper_bound(yPos.begin(), yPos.end(), nearestR) - yPos.begin()), 0ll);
            // }
            int newRes = dp(RR + 1, GG, YY, 0) + ad;
            // DBG2(idx, lastUsed);
            // DBG3(ad, max(nearestR - idx, 0ll), newRes);
            res = min(res, newRes);
        }
     
        if (GG < G && lastUsed != 1) {
            int nearestG = gPos[GG], ad = 0;
            // if (idx >= nearestG) {
                ad += max(RR - (upper_bound(rPos.begin(), rPos.end(), nearestG) - rPos.begin()), 0ll);
                ad += max(YY - (upper_bound(yPos.begin(), yPos.end(), nearestG) - yPos.begin()), 0ll);
            // }
            int newRes = dp(RR, GG + 1, YY, 1) + ad;
            res = min(res, newRes);
        }
     
        if (YY < Y && lastUsed != 2) {
            int nearestY = yPos[YY], ad = 0;
            // if (idx >= nearestY) {
                ad += max(RR - (upper_bound(rPos.begin(), rPos.end(), nearestY) - rPos.begin()), 0ll);
                ad += max(GG - (upper_bound(gPos.begin(), gPos.end(), nearestY) - gPos.begin()), 0ll);
            // }
            int newRes = dp(RR, GG, YY + 1, 2) + ad;
            // DBG2(idx, lastUsed);
            // DBG3(ad, max(nearestY - idx, 0ll), newRes);
            res = min(res, newRes);
        }
     
        memo[{RR, GG, YY, lastUsed}] = res;
        return res;
    }
     
    void dp2(int RR, int GG, int YY, int lastUsed) {
        if (RR == R && GG == G && YY == Y) return;
        int res = 1e18;
        char c;
        tuple<int, int, int, int> t = { -1, -1, -1, -1 };
     
        if (RR < R && lastUsed != 0) {
            if (memo[{RR + 1, GG, YY, 0}] < res) {
                res = memo[{RR + 1, GG, YY, 0}];
                t = { RR + 1, GG, YY, 0 };
                c = 'R';
            }
        }
     
        if (GG < G && lastUsed != 1) {
            if (memo[{RR, GG + 1, YY, 1}] < res) {
                res = memo[{RR, GG + 1, YY, 1}];
                t = { RR, GG + 1, YY, 1 };
                c = 'G';
            }
        }
     
        if (YY < Y && lastUsed != 2) {
            if (memo[{RR, GG, YY + 1, 2}] < res) {
                res = memo[{RR, GG, YY + 1, 2}];
                t = { RR, GG, YY + 1, 2 };
                c = 'Y';
            }
        }
        A += c;
     
        int a, b, cc, d;
        tie(a, b, cc, d) = t;
        DBG4(a, b, cc, d);
        DBG1(res);
        dp2(a, b, cc, d);
    }
     
    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);
            }
        }
        int res = dp(0, 0, 0, -1);
        if (res >= 1e18) cout << -1 << endl;
        else {
            cout << res << endl;
        }
    }

Compilation message

joi2019_ho_t3.cpp: In function 'long long int dp(long long int, long long int, long long int, long long int)':
joi2019_ho_t3.cpp:53:25: warning: unused variable 'idx' [-Wunused-variable]
   53 |         int res = 1e18, idx = RR + GG + YY;
      |                         ^~~
joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:31:34: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 |     #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                                  ^
joi2019_ho_t3.cpp:136:9: note: in expansion of macro 'FOR'
  136 |         FOR(i, 0, N) {
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 6 ms 1364 KB Output is correct
19 Correct 6 ms 1236 KB Output is correct
20 Correct 6 ms 1236 KB Output is correct
21 Correct 7 ms 1364 KB Output is correct
22 Correct 4 ms 980 KB Output is correct
23 Correct 6 ms 1364 KB Output is correct
24 Correct 4 ms 852 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 7 ms 1364 KB Output is correct
29 Correct 7 ms 1376 KB Output is correct
30 Correct 6 ms 1236 KB Output is correct
31 Correct 6 ms 1180 KB Output is correct
32 Correct 6 ms 1308 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 5 ms 1108 KB Output is correct
36 Correct 6 ms 1236 KB Output is correct
37 Correct 4 ms 980 KB Output is correct
38 Correct 5 ms 1108 KB Output is correct
39 Correct 7 ms 1344 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 6 ms 1364 KB Output is correct
19 Correct 6 ms 1236 KB Output is correct
20 Correct 6 ms 1236 KB Output is correct
21 Correct 7 ms 1364 KB Output is correct
22 Correct 4 ms 980 KB Output is correct
23 Correct 6 ms 1364 KB Output is correct
24 Correct 4 ms 852 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 7 ms 1364 KB Output is correct
29 Correct 7 ms 1376 KB Output is correct
30 Correct 6 ms 1236 KB Output is correct
31 Correct 6 ms 1180 KB Output is correct
32 Correct 6 ms 1308 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 5 ms 1108 KB Output is correct
36 Correct 6 ms 1236 KB Output is correct
37 Correct 4 ms 980 KB Output is correct
38 Correct 5 ms 1108 KB Output is correct
39 Correct 7 ms 1344 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 0 ms 340 KB Output is correct
53 Correct 0 ms 340 KB Output is correct
54 Correct 1 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Execution timed out 1092 ms 125808 KB Time limit exceeded
59 Halted 0 ms 0 KB -