제출 #119990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119990		tutis	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	63 ms	31096 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 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();
	int dp[p[0].size() + 2][p[1].size() + 2][p[2].size() + 2][3];
	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;
	int d[3][n][n];
	for (int a = 0; a < 3; a++)
	{
		for (int i = 0; i < n; i++)
		{
			auto it = lower_bound(p[a].begin(), p[a].end(), i);
			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 = 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]][k[1]][k[2]][0]);
						dp[k[0] + 1][k[1]][k[2]][2] =
						    min(dp[k[0] + 1][k[1]][k[2]][2],
						        cost + dp[k[0]][k[1]][k[2]][0]);
					}
					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]][k[2]][1]);
						dp[k[0]][k[1] + 1][k[2]][2] =
						    min(dp[k[0]][k[1] + 1][k[2]][2],
						        cost + dp[k[0]][k[1]][k[2]][1]);
					}
					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]][2]);
						dp[k[0]][k[1]][k[2] + 1][1] =
						    min(dp[k[0]][k[1]][k[2] + 1][1],
						        cost + dp[k[0]][k[1]][k[2]][2]);
					}
				}
			}
		}
	}
	int ans = min({dp[p0s][p1s][p2s][0],
	               dp[p0s][p1s][p2s][1],
	               dp[p0s][p1s][p2s][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