Submission #119987

#	Time	Username	Problem	Language	Result	Execution time	Memory
119987		tutis	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	1066 ms	121920 KiB

joi2019_ho_t3

/*input
5
RRGYY
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
unordered_map<bitset<1200>, int>M[3];
bitset<1200>xx[400];
int dp(bitset<1200>s, int x, int n)
{
	if (M[x].count(s))
		return M[x][s];
	if (n == 1)
	{
		for (int i = 0; i < 400; i++)
			if (s[400 * x + i])
				return M[x][s] = 0;
		return M[x][s] = 1e8 + 5;
	}
	int i = s._Find_next(x * 400 - 1) - 400 * x;
	if (i < 400)
	{
		int cost = (s & xx[i]).count() - 1;
		bitset<1200>ss = s;
		ss[x * 400 + i] = false;
		int mini = 3e8;
		for (int y = 0; y <= 2; y++)
		{
			if (x != y)
			{
				mini = min(mini, dp(ss, y, n - 1));
			}
		}
		return M[x][s] = cost + mini;
	}
	return M[x][s] = 3e8;
}
int code(char c)
{
	if (c == 'R')
		return 0;
	if (c == 'G')
		return 1;
	return 2;
}
int main()
{
	bitset<1200>aa;
	for (int i = 0; i < 400; i++)
	{
		aa[i] = aa[400 + i] = aa[800 + i] = true;
		xx[i] = aa;
	}
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	bitset<1200>ss;
	for (int i = 0; i < n; i++)
	{
		ss[400 * code(s[i]) + i] = true;
	}
	int ans = min({dp(ss, 0, n), dp(ss, 1, n), dp(ss, 2, n)});
	if (ans > 1e8)
		ans = -1;
	cout << ans << "\n";
}

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