Submission #1186161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186161		patgra	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	93 ms	26696 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int inf = 1e9 + 7;
map<char, int> xd = { {'R', 0}, {'G', 1}, {'Y', 2} };

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<vector<vector<int>>>> dp(2, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(n + 1, vector<int>(3))));
    vector<vector<vector<vector<array<int, 3>>>>> skond;
    DEBUG skond.resize(n + 1, vector<vector<vector<array<int, 3>>>>(n + 1, vector<vector<array<int, 3>>>(n + 1, vector<array<int, 3>>(3))));
    vector<vector<pair<int, int>>> where(3);
    rep(i, 0, n) where[xd[s[i]]].pb({i, where[(xd[s[i]] ? 0 : 1)].size()});
    rep(i, 0, n + 1) {
        rep(c1, 0, (int)where[0].size() + 1) rep(c2, 0, (int)where[1].size() + 1) rep(last, 0, 3) dp[i & 1][c1][c2][last] = inf;
        rep(c1, 0, min(i + 1, (int)where[0].size() + 1)) rep(c2, 0, min(i - c1 + 1, (int)where[1].size() + 1)) {
            auto c3 = i - c1 - c2;
            if(c3 < 0 || c3 > where[2].size()) continue;
            DC << i << ' ' << c1 << ' ' << c2 << "   ";
            rep(last, 0, 3) {
                auto me = dp[1 ^ (i & 1)][c1][c2][last];
                if(me == inf) { DC << "oo "; }
                else DC << me << ' ';
                if(i == 3 && me == 1) {
                    DC << "";
                }
                rep(last2, 0, 3) {
                    if(i == n || last == last2) continue;
                    if(last2 == 2 && c3 < (int)where[2].size()) {
                        if(i == 3 && c1 == 2 && c2 == 1 && last == 0) 
                            DC << "siusiak";
                        auto [ogPos, b1] = where[2][c3];
                        int b3 = c3;
                        int b2 = min(ogPos - b1 - b3, c2);
                        b1 = min(b1, c1);
                        dp[i & 1][c1][c2][last2] = min(dp[i & 1][c1][c2][last2], me + max(ogPos - b1 - b2 - b3, 0));
                        DEBUG if(dp[i & 1][c1][c2][last2] == me + max(ogPos - b1 - b2 - b3, 0)) skond[i + 1][c1][c2][last2] = {c1, c2, last};
                    }
                    if(last2 == 1 && c2 < (int)where[1].size()) {
                        auto [ogPos, b1] = where[1][c2];
                        int b2 = c2;
                        int b3 = min(ogPos - b1 - b2, c3);
                        b1 = min(b1, c1);
                        dp[i & 1][c1][c2 + 1][last2] = min(dp[i & 1][c1][c2 + 1][last2], me + max(ogPos - b1 - b2 - b3, 0)); 
                        DEBUG if(dp[i & 1][c1][c2 + 1][last2] == me + max(ogPos - b1 - b2 - b3, 0)) skond[i + 1][c1][c2 + 1][last2] = {c1, c2, last};
                    }
                    if(last2 == 0 && c1 < (int)where[0].size()) {
                        auto [ogPos, b2] = where[0][c1];
                        int b1 = c1;
                        int b3 = min(ogPos - b1 - b2, c3);
                        b2 = min(b2, c2);
                        dp[i & 1][c1 + 1][c2][last2] = min(dp[i & 1][c1 + 1][c2][last2], me + max(ogPos - b1 - b2 - b3, 0));
                        DEBUG if(dp[i & 1][c1 + 1][c2][last2] == me + max(ogPos - b1 - b2 - b3, 0)) skond[i + 1][c1 + 1][c2][last2] = {c1, c2, last};
                    }
                }
            }
            DC << "   \t\t";
            rep(last, 0, 3) {
                auto [pc1, pc2, pls] = skond[i][c1][c2][last];
                DC << "(" << pc1 << ' ' << pc2 << ' ' << pls << ") \t";
            }
            DC << eol;
        }
    }
    int ans = inf;
    rep(last, 0, 3) ans = min(ans, dp[(1 ^ n) & 1][where[0].size()][where[1].size()][last]);
    if(ans == inf) ans = -1;
    cout << ans << '\n';
}

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