oj.uz

Submission #119979

# Submission time Handle Problem Language Result Execution time Memory
119979 2019-06-22T20:34:27 Z tutis Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 9 ms 1280 KB 
/*input
20
YYGYYYGGGGRGYYGRGRYG
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
map<tuple<int, int, int, int>, int>M;
int dp(bitset<400>s[3], int x, int n)
{
	int h1 = hash<bitset<400>>()(s[0]);
	int h2 = hash<bitset<400>>()(s[1]);
	int h3 = hash<bitset<400>>()(s[2]);
	if (M.count(make_tuple(h1, h2, h3, x)))
		return M[make_tuple(h1, h2, h3, x)];
	if (n == 1)
	{
		if (s[x][0])
			return 0;
		else
			return 3e8;
	}
	for (int i = n - 1; i >= 0; i--)
	{
		if (s[x][i])
		{
			bitset<400>ss[3] = {s[0], s[1], s[2]};
			ss[x][i] = 0;
			for (int j = i; j + 1 < n; j++)
			{
				ss[0][j] = ss[0][j + 1];
				ss[1][j] = ss[1][j + 1];
				ss[2][j] = ss[2][j + 1];
			}
			int cost = (n - 1) - i;
			int mini = 3e8;
			for (int y = 0; y < 3; y++)
			{
				if (x != y)
				{
					mini = min(mini, dp(ss, y, n - 1));
				}
			}
			return M[make_tuple(h1, h2, h3, x)] = cost + mini;
		}
	}
	return M[make_tuple(h1, h2, h3, x)] = 3e8;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	bitset<400>ss[3];
	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'R')
			ss[0][i] = true;
		if (s[i] == 'G')
			ss[1][i] = true;
		if (s[i] == 'Y')
			ss[2][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 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 7 ms 996 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Incorrect 3 ms 512 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 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 7 ms 996 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Incorrect 3 ms 512 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 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 484 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 7 ms 996 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Incorrect 3 ms 512 KB Output isn't correct
15 Halted 0 ms 0 KB -