Submission #119992

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

joi2019_ho_t3

/*input
20
YYGYYYGGGGRGYYGRGRYG

*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#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 dp[402][402][402][3];
int d[3][402][402];
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);
	const int p0s = p[0].size();
	const int p1s = p[1].size();
	const int p2s = p[2].size();
	if (max({p0s, p1s, p2s}) > (n + 1) / 2)
	{
		cout << "-1\n";
		return 0;
	}
	for (int k0 = 0; k0 <= p0s; k0++)
	{
		for (int k1 = 0; k1 <= p1s; k1++)
		{
			for (int k2 = 0; k2 <= p2s; 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;
	for (int a = 0; a < 3; a++)
	{
		auto it = p[a].begin();
		for (int i = 0; i < n; i++)
		{
			while (it != p[a].end() && (*it) < i)
				it++;
			for (int k = 0; k <= (int)p[a].size(); k++)
			{
				d[a][i][k] = max(it, p[a].begin() + k) - (p[a].begin() + k);
			}
		}
	}
	int k[3];
	for (k[0] = 0; k[0] <= p0s; k[0]++)
	{
		for (k[1] = 0; k[1] <= p1s; k[1]++)
		{
			for (k[2] = 0; k[2] <= p2s; k[2]++)
			{
				for (int a = 0; a < 3; a++)
				{
					if (k[a] == (int)p[a].size())
						continue;
					int cost = dp[k[0]][k[1]][k[2]][a] + d[0][p[a][k[a]]][k[0]] + d[1][p[a][k[a]]][k[1]] + d[2][p[a][k[a]]][k[2]];
					if (a == 0)
					{
						dp[k[0] + 1][k[1]][k[2]][1] =
						    min(dp[k[0] + 1][k[1]][k[2]][1],
						        cost);
						dp[k[0] + 1][k[1]][k[2]][2] =
						    min(dp[k[0] + 1][k[1]][k[2]][2],
						        cost);
					}
					else if (a == 1)
					{
						dp[k[0]][k[1] + 1][k[2]][0] =
						    min(dp[k[0]][k[1] + 1][k[2]][0],
						        cost);
						dp[k[0]][k[1] + 1][k[2]][2] =
						    min(dp[k[0]][k[1] + 1][k[2]][2],
						        cost);
					}
					else
					{
						dp[k[0]][k[1]][k[2] + 1][0] =
						    min(dp[k[0]][k[1]][k[2] + 1][0],
						        cost);
						dp[k[0]][k[1]][k[2] + 1][1] =
						    min(dp[k[0]][k[1]][k[2] + 1][1],
						        cost);
					}
				}
			}
		}
	}
	int ans = min({dp[p0s][p1s][p2s][0],
	               dp[p0s][p1s][p2s][1],
	               dp[p0s][p1s][p2s][2]
	              });
	cout << ans << "\n";
}

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