Submission #923803

#	Time	Username	Problem	Language	Result	Execution time	Memory
923803		HorizonWest	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	246 ms	134736 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]++;
    }
/*
    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;
    }*/

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

    vector <vector<vector<vector<int>>>> dp(rz + 1,  vector <vector<vector<int>>> (gz + 1,
                   vector <vector<int>> (yz + 1, vector <int> (3, Inf))));
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= min(rz, i + 1); j++)
        {
            for(int k = 0; 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)
                    {
                        int gx = 0, yx = 0, pj = r[j - 1];
                        gx = max(0, k - gs[pj]);
                        yx = max(0, l - ys[pj]);
                        pj += gx + yx;
                        dp[j][k][l][0] = min(dp[j][k][l][0], min(dp[j - 1][k][l][1], dp[j - 1][k][l][2]) + abs(pj - i));
                    }

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

                    if(l > 0)
                    {
                        int rx = 0, gx = 0, pl = y[l - 1];//if(i == n - 1) dbg(pl);
                        rx = max(0, j - rs[pl]);
                        gx = max(0, k - gs[pl]);
                        pl += rx + gx;
                        dp[j][k][l][2] = min(dp[j][k][l][2], min(dp[j][k][l - 1][0], dp[j][k][l - 1][1]) + abs(pl - 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