Submission #119989

#	Time	Username	Problem	Language	Result	Execution time	Memory
119989		tutis	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	65 ms	31132 KiB

joi2019_ho_t3

/*input
20
YYGYYYGGGGRGYYGRGRYG

*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int code(char c)
{
	if (c == 'R')
		return 0;
	if (c == 'G')
		return 1;
	return 2;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	vector<int>p[3];
	for (int i = 0; i < n; i++)
		p[code(s[i])].push_back(i);
	int dp[p[0].size() + 2][p[1].size() + 2][p[2].size() + 2][3];
	for (int k0 = 0; k0 <= (int)p[0].size(); k0++)
	{
		for (int k1 = 0; k1 <= (int)p[1].size(); k1++)
		{
			for (int k2 = 0; k2 <= (int)p[2].size(); k2++)
			{
				for (int a = 0; a < 3; a++)
					dp[k0][k1][k2][a] = 2e8;
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	int d[3][n][n];
	for (int a = 0; a < 3; a++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int k = 0; k <= (int)p[a].size(); k++)
			{
				d[a][i][k] = lower_bound(p[a].begin() + k, p[a].end(), i) - (p[a].begin() + k);
			}
		}
	}
	int k[3];
	for (k[0] = 0; k[0] <= (int)p[0].size(); k[0]++)
	{
		for (k[1] = 0; k[1] <= (int)p[1].size(); k[1]++)
		{
			for (k[2] = 0; k[2] <= (int)p[2].size(); k[2]++)
			{
				for (int a = 0; a < 3; a++)
				{
					if (k[a] == (int)p[a].size())
						continue;
					int cost = d[0][p[a][k[a]]][k[0]] + d[1][p[a][k[a]]][k[1]] + d[2][p[a][k[a]]][k[2]];
					for (int b = 0; b < 3; b++)
					{
						if (a == b)
							continue;
						dp[k[0] + (a == 0)][k[1] + (a == 1)][k[2] + (a == 2)][b] =
						    min(dp[k[0] + (a == 0)][k[1] + (a == 1)][k[2] + (a == 2)][b],
						        cost + dp[k[0]][k[1]][k[2]][a]);
					}
				}
			}
		}
	}
	int ans = min({dp[p[0].size()][p[1].size()][p[2].size()][0],
	               dp[p[0].size()][p[1].size()][p[2].size()][1],
	               dp[p[0].size()][p[1].size()][p[2].size()][2]
	              });
	if (ans > 1e8)
		ans = -1;
	cout << ans << "\n";
}

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