제출 #1162658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162658		abysmal	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	75 / 100	1100 ms	101140 KiB

joi2019_ho_t3

#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<vector<int> > > > > dp(2, vector<vector<vector<vector<int> > > >(k, vector<vector<vector<int> > >(r, vector<vector<int> >(g, vector<int>(y, mINF)))));

        if(r > 1) dp[0][0][1][0][0] = colors[0][0];
        if(g > 1) dp[0][1][0][1][0] = colors[1][0];
        if(y > 1) dp[0][2][0][0][1] = 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++)
                    {
                        for(int cy = 0; cy < y; cy++)
                        {
                            if(dp[p][last][cr][cg][cy] == mINF) continue;

                            // 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][cy] = min(dp[t][b][cr + 1][cg][cy], dp[p][last][cr][cg][cy] + 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][cy] = min(dp[t][b][cr][cg + 1][cy], dp[p][last][cr][cg][cy] + 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][cy + 1] = min(dp[t][b][cr][cg][cy + 1], dp[p][last][cr][cg][cy] + cost); 
                            }
                        }
                    }
                }
            }

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

        int ans = mINF;
        for(int last = 0; last < k; last++)
        {
            ans = min(ans, dp[t ^ 1][last][r - 1][g - 1][y - 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);
    cout.tie(nullptr);
	int t = 1;
	//cin >> t;
	for(int i = 0; i < t; i++)
	{
		Solution().solve();
	}
	return 0;
}

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