Submission #871929

#	Time	Username	Problem	Language	Result	Execution time	Memory
871929		HorizonWest	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	214 ms	133824 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
//#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

//int dp[70][70][70][3];

void solve()
{
    int n; string s; cin >> n >> s;
    vector <int> r, g, y, rs(n), gs(n), ys(n);
    for(int i = 0; i < n; i++)
    {
        if(i != 0)
        {
            rs[i] = rs[i - 1];
            gs[i] = gs[i - 1];
            ys[i] = ys[i - 1];
        }

        if(s[i] == 'R') r.pb(i), rs[i]++;
        if(s[i] == 'G') g.pb(i), gs[i]++;
        if(s[i] == 'Y') y.pb(i), ys[i]++;
    }

    int rz = r.size(), gz = g.size(), yz = y.size();

    int mx = 0; mx = max(rz, max(gz, yz));

    if(rz == mx)
    {
        swap(r, y);
        swap(rs, ys);
        swap(rz, yz);
    }

    if(gz == mx)
    {
        swap(g, y);
        swap(gs, ys);
        swap(gz, yz);
    }

/*
    for(int i = 0; i < n + 7; i++)
    {
        for(int j = 0; j < n + 7; j ++)
            for(int k = 0; k < n + 7; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = Inf;
    }*/

    vector <vector<vector<vector<int>>>> dp(rz + 1,  vector <vector<vector<int>>> ());


   // vector <vector<vector<vector<int>>>> dp(rz + 1,  vector <vector<vector<int>>> (gz + 1,
   //                vector <vector<int>> (yz + 1, vector <int> (3, Inf))));

    for(int i = 0; i < rz + 1; i++)
    {
        dp[i].assign(min(gz + 1, n - i + 1), vector <vector<int>> ()); 
        for(int j = 0; j < min(gz + 1, n - i + 1); j++)
        {
            dp[i][j].assign(min(yz + 1, n - (i + j) + 1), vector <int> (3, Inf)); 
        }
    }

   //cout  << "WA";
   //return; 
    
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0; int val; 

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= min(rz, i + 1); j++)
        {
            for(int k = max(0, (i + 1) - (yz + j)); k + j <= i + 1 && k <= gz; k++)
            {
                //for(int l = 0; l + k + j <= i + 1 && l <= yz; l++)
                //{
                    //if(j + k + l != i + 1) continue;
                    int l = (i + 1) - (j + k);
                    //if(l > yz) continue;

                    if(j > 0)
                    {
                        val = r[j - 1] + max(0, k - gs[r[j - 1]]) + max(0, l - ys[r[j - 1]]);
                        dp[j][k][l][0] = min(dp[j - 1][k][l][1], dp[j - 1][k][l][2]) + abs(val - i);
                    }

                    if(k > 0)
                    {
                        val = g[k - 1] + max(0, j - rs[g[k - 1]]) + max(0, l - ys[g[k - 1]]);
                        dp[j][k][l][1] = min(dp[j][k - 1][l][0], dp[j][k-1][l][2]) + abs(val - i);
                    }

                    if(l > 0)
                    {
                        val = y[l - 1] + max(0, j - rs[y[l - 1]]) + max(0, k - gs[y[l - 1]]);
                        dp[j][k][l][2] = min(dp[j][k][l - 1][0], dp[j][k][l - 1][1]) + abs(val - i);
                    }

                    //cout << i << " " << j << " " << k << " " << l << " " << endl;
                    // dbg(dp[j][k][l][0]); dbg(dp[j][k][l][1]); dbg(dp[j][k][l][2]);
                //}
            }
        }
    }

    int ans = min(dp[rz][gz][yz][0], min(dp[rz][gz][yz][1], dp[rz][gz][yz][2]));

    cout << (ans >= Inf ? -1 : ans) << endl;
}

/*
5
RRGYY
*/

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int Q = 1; //cin >> Q;

	while (Q--)
	{
		solve();
	}

	return 0;
}

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