Submission #1162664

#TimeUsernameProblemLanguageResultExecution timeMemory
1162664abysmalGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
67 ms1864 KiB
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stdint.h>
#include<vector>

#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...)
#endif

using namespace std;

const int64_t INF = (int64_t) 1e18 + 777;
const int64_t mINF = (int64_t) 1e9 + 777;
const int64_t MOD = (int64_t) 1e9 + 7;

struct Solution
{
	Solution() {}

	void solve()
	{
        int n;
        string s;
        cin >> n >> s;
        int k = 3;
        vector<vector<int> > colors(k);

        // ???
        for (int i = 0; i < k; i++) {
            colors.reserve(n);
        }

        vector<vector<int> > prefix(k, vector<int>(n + 1, 0));

        for(int i = 0; i < n; i++)
        {
            int x = getID(s[i]);
            colors[x].push_back(i);
            prefix[x][i + 1] = 1;
        }

        for(int i = 0; i < k; i++)
        {
            colors[i].push_back(n);
            // sort(colors[i].begin(), colors[i].end());

            for(int j = 1; j <= n; j++)
            {
                prefix[i][j] += prefix[i][j - 1];
            }
        }

        int r = colors[0].size();
        int g = colors[1].size();
        int y = colors[2].size();
        vector<vector<vector<vector<int> > > > dp(2, vector<vector<vector<int > > >(k, vector<vector<int> >(r, vector<int>(g, mINF))));

        if(r > 1) dp[0][0][1][0] = colors[0][0];
        if(g > 1) dp[0][1][0][1] = colors[1][0];
        if(y > 1) dp[0][2][0][0] = colors[2][0];
        int t = 1;
        for(int i = 1; i < n; i++)
        {
            int p = t ^ 1;
            for(int last = 0; last < k; last++)
            {
                for(int cr = 0; cr < r; cr++)
                {
                    for(int cg = 0; cg < g; cg++)
                    {
                        if(dp[p][last][cr][cg] == mINF) continue;

                        int cy = i - cr - cg;
                        // red
                        // A = last B = now C = other
                        if(last != 0 && cr != r - 1)
                        {
                            int a = last;
                            int b = 0;
                            int c = 0;

                            int cur_a = 0;
                            int cur_c = 0;
                            int cur_b = colors[b][cr];
                            if(a == 1)
                            {
                                c = 2;
                                cur_a = colors[a][cg];
                                cur_c = colors[c][cy];
                            }
                            else
                            {
                                c = 1;
                                cur_a = colors[a][cy];
                                cur_c = colors[c][cg];
                            }

                            int cnt1 = prefix[a][cur_b + 1] - prefix[a][cur_a];
                            int cnt2 = prefix[c][cur_b + 1] - prefix[c][cur_c];
                            cnt1 = max(cnt1, 0); cnt2 = max(cnt2, 0);

                            int cost = cnt1 + cnt2;
                            dp[t][b][cr + 1][cg] = min(dp[t][b][cr + 1][cg], dp[p][last][cr][cg] + cost);
                        }

                        // green
                        if(last != 1 && cg != g - 1)
                        {
                            int a = last;
                            int b = 1;
                            int c = 0;

                            int cur_a = 0;
                            int cur_c = 0;
                            int cur_b = colors[b][cg];
                            if(a == 0)
                            {
                                c = 2;
                                cur_a = colors[a][cr];
                                cur_c = colors[c][cy];
                            }
                            else
                            {
                                c = 0;
                                cur_a = colors[a][cy];
                                cur_c = colors[c][cr];
                            }

                            int cnt1 = prefix[a][cur_b + 1] - prefix[a][cur_a];
                            int cnt2 = prefix[c][cur_b + 1] - prefix[c][cur_c];
                            cnt1 = max(cnt1, 0); cnt2 = max(cnt2, 0);
                            int cost = cnt1 + cnt2;
                            dp[t][b][cr][cg + 1] = min(dp[t][b][cr][cg + 1], dp[p][last][cr][cg] + cost);
                        }

                        // yellow
                        if(last != 2 && cy != y - 1)
                        {
                            int a = last;
                            int b = 2;
                            int c = 0;

                            int cur_a = 0;
                            int cur_c = 0;
                            int cur_b = colors[b][cy];
                            if(a == 0)
                            {
                                c = 1;
                                cur_a = colors[a][cr];
                                cur_c = colors[c][cg];
                            }
                            else
                            {
                                c = 0;
                                cur_a = colors[a][cg];
                                cur_c = colors[c][cr];
                            }

                            int cnt1 = prefix[a][cur_b + 1] - prefix[a][cur_a];
                            int cnt2 = prefix[c][cur_b + 1] - prefix[c][cur_c];
                            cnt1 = max(cnt1, 0); cnt2 = max(cnt2, 0);

                            int cost = cnt1 + cnt2;
                            dp[t][b][cr][cg] = min(dp[t][b][cr][cg], dp[p][last][cr][cg] + cost);
                        }
                    }
                }
            }

            for(int last = 0; last < k; last++)
            {
                for(int cr = 0; cr < r; cr++)
                {
                    for(int cg = 0; cg < g; cg++)
                    {
                         dp[p][last][cr][cg] = mINF;
                    }
                }
            }
            t ^= 1;
        }

        int ans = mINF;
        for(int last = 0; last < k; last++)
        {
            ans = min(ans, dp[t ^ 1][last][r - 1][g - 1]);
        }
        if(ans == mINF) ans = -1;
        cout << ans << "\n";
	}

    int getID(char c)
    {
        if(c == 'R') return 0;
        if(c == 'G') return 1;
        if(c == 'Y') return 2;
        return -1;
    }

	int modadd(int a, int b)
	{
		int res = a + b;
		if(res >= MOD) res -= MOD;
		return res;
	}

	int modmul(int a, int b)
	{
		return (1LL * a * b) % MOD;
	}
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	int t = 1;
	//cin >> t;
	for(int i = 0; i < t; i++)
	{
		Solution().solve();
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...