Submission #119973

#	Time	Username	Problem	Language	Result	Execution time	Memory
119973		tutis	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	1062 ms	71400 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;
map<pair<string, char>, int>M;
int dp(string s, char x)
{
	if (M.count({s, x}))
		return M[ {s, x}];
	if (s.size() == 1)
	{
		if (s[0] == x)
			return 0;
		else
			return 3e8;
	}
	int cost = 0;
	for (int i = s.size() - 1; i >= 0; i--)
	{
		if (s[i] == x)
		{
			cost += (int)s.size() - i - 1;
			string ss = s;
			s.erase(s.begin() + i);
			int mini = 3e8;
			for (char y : {'R', 'G', 'Y'})
			{
				if (y == x)
					continue;
				mini = min(mini, dp(s, y));
			}
			return M[ {ss, x}] = cost + mini;
		}
	}
	return M[ {s, x}] = 3e8;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	int ans = min({dp(s, 'R'), dp(s, 'G'), dp(s, 'Y')});
	if (ans > 1e8)
		ans = -1;
	cout << ans << "\n";
}

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