Submission #119981

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
119981	2019-06-22T20:47:20 Z	tutis	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	12 ms	3200 KB

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;
unordered_map<bitset<1203>, int>M;
int dp(bitset<1203>s, int x, int n)
{
	s[1200] = (x == 0);
	s[1201] = (x == 1);
	s[1202] = (x == 2);
	if (n == 1)
	{
		if (s[x * 400])
			return 0;
		else
			return 1e8 + 5;
	}
	if (M.count(s))
		return M[s];
	for (int i = n - 1; i >= 0; i--)
	{
		if (s[x * 400 + i])
		{
			bitset<1203>ss = s;
			ss[x * 400 + i] = false;
			for (int j = i; j + 1 < n; j++)
			{
				ss[000 + j] = ss[000 + j + 1];
				ss[400 + j] = ss[400 + j + 1];
				ss[800 + j] = ss[800 + j + 1];
			}
			int cost = (n - 1) - i;
			int mini = 1e8 + 5;
			for (int y = 0; y <= 2; y++)
			{
				if (x != y)
				{
					mini = min(mini, dp(ss, y, n - 1));
				}
			}
			return M[s] = cost + mini;
		}
	}
	return M[s] = 3e8;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	bitset<1203>ss;
	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'R')
			ss[000 + i] = true;
		if (s[i] == 'G')
			ss[400 + i] = true;
		if (s[i] == 'Y')
			ss[800 + 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

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	320 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	4 ms	896 KB	Output is correct
6	Correct	12 ms	3200 KB	Output is correct
7	Correct	8 ms	2276 KB	Output is correct
8	Correct	8 ms	1920 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	4 ms	896 KB	Output is correct
12	Correct	7 ms	1792 KB	Output is correct
13	Correct	3 ms	552 KB	Output is correct
14	Incorrect	3 ms	896 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	320 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	4 ms	896 KB	Output is correct
6	Correct	12 ms	3200 KB	Output is correct
7	Correct	8 ms	2276 KB	Output is correct
8	Correct	8 ms	1920 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	4 ms	896 KB	Output is correct
12	Correct	7 ms	1792 KB	Output is correct
13	Correct	3 ms	552 KB	Output is correct
14	Incorrect	3 ms	896 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	3 ms	796 KB	Output is correct
4	Correct	3 ms	768 KB	Output is correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	4 ms	768 KB	Output is correct
9	Correct	3 ms	768 KB	Output is correct
10	Correct	3 ms	812 KB	Output is correct
11	Correct	3 ms	768 KB	Output is correct
12	Correct	8 ms	512 KB	Output is correct
13	Correct	3 ms	640 KB	Output is correct
14	Correct	3 ms	640 KB	Output is correct
15	Correct	3 ms	768 KB	Output is correct
16	Correct	3 ms	812 KB	Output is correct

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	320 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	4 ms	896 KB	Output is correct
6	Correct	12 ms	3200 KB	Output is correct
7	Correct	8 ms	2276 KB	Output is correct
8	Correct	8 ms	1920 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	4 ms	896 KB	Output is correct
12	Correct	7 ms	1792 KB	Output is correct
13	Correct	3 ms	552 KB	Output is correct
14	Incorrect	3 ms	896 KB	Output isn't correct
15	Halted	0 ms	0 KB	-