Submission #110631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
110631	2019-05-11T17:48:41 Z	qkxwsm	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	462 ms	380956 KB

joi2019_ho_t3

//clever
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

random_device(rd);
mt19937 rng(rd());
const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

struct custom_hash
{
	template<class T>
	unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x += FIXED_RANDOM;
		// x += 11400714819323198485ull;
		// x = (x ^ (x >> 30)) * 13787848793156543929ull;
		x = (x ^ (x >> 27)) * 10723151780598845931ull;
		return x ^ (x >> 31);
	}
};

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;

template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}
template<class T>
void readi(T &x)
{
	x = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		x = -x;
	}
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int buf[20], n = 0;
	while(output)
	{
		buf[n] = ((output % 10));
		output /= 10;
		n++;
	}
	for (n--; n >= 0; n--)
	{
		putchar(buf[n] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long expo(long long a, long long e, long long mod)
{
	return ((e == 0) ? 1 : ((expo(a * a % mod, e >> 1, mod)) * ((e & 1) ? a : 1) % mod));
}
template<class T, class U>
void nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define SZ(x) ((int) ((x).size()))
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-9;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 413

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pdd> vpd;

int N;
int arr[MAXN];
vi pos[3];
int ans = INF;
int pref[MAXN][3];
int dp[MAXN][MAXN][MAXN][3];

int qry(int l, int r, int num)
{
	if (l > r) return 0;
	// cerr << num << ' ' << l << ' ' << r << ' ' << pref[r + 1][num] - pref[l][num] << endl;
	return pref[r + 1][num] - pref[l][num];
}
int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	// cout << fixed << setprecision(10);
	// cerr << fixed << setprecision(10);
	// if (fopen("file.in", "r"))
	// {
	// 	freopen ("file.in", "r", stdin);
	// 	freopen ("file.out", "w", stdout);
	// }
	cin >> N;
	string temps; cin >> temps;
	FOR(i, 0, N)
	{
		if (temps[i] == 'R') arr[i] = 0;
		if (temps[i] == 'G') arr[i] = 1;
		if (temps[i] == 'Y') arr[i] = 2;
		pos[arr[i]].PB(i);
		FOR(j, 0, 3)
		{
			pref[i + 1][j] = pref[i][j] + (arr[i] == j);
		}
	}

	FOR(i, 0, N + 1)
	{
		FOR(j, 0, i + 1)
		{
			for (int k = 0; k + j <= i; k++)
			{
				dp[i][j][k][0] = INF;
				dp[i][j][k][1] = INF;
				dp[i][j][k][2] = INF;
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	FOR(i, 0, N)
	{
		int n[3];
		for (n[0] = 0; n[0] <= i; n[0]++)
		{
			for (n[1] = 0; n[0] + n[1] <= i; n[1]++)
			{
				n[2] = i - n[0] - n[1];
				FOR(k, 0, 3)
				{
					if (n[k] >= SZ(pos[k])) continue;
					int curpos = pos[k][n[k]];
					//you also shift it to the right, equal
					FOR(j, 0, 3)
					{
						if (j == k) continue;
						curpos += max(0, n[j] - qry(0, pos[k][n[k]] - 1, j));
					}
					int c = abs(curpos - i);
					FOR(j, 0, 3)
					{
						if (j == k) continue;
						ckmin(dp[i + 1][n[0] + (k == 0)][n[1] + (k == 1)][k], dp[i][n[0]][n[1]][j] + c);
					}
				}
			}
		}
	}
	FOR(i, 0, N + 1)
	{
		for (int j = 0; i + j <= N; j++)
		{
			ckmin(ans, dp[N][i][j][0]);
			ckmin(ans, dp[N][i][j][1]);
			ckmin(ans, dp[N][i][j][2]);
		}
	}
	if (ans == INF)
	{
		cout << "-1\n";
		return 0;
	}
	cout << ans << '\n';
	// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}
/* READ READ READ
* int overflow, maxn too small, special cases (n=1?, two distinct?), cin.tie() interactive
* reread the problem, try small cases
* note down possible sources of error as you go
* do smth instead of nothing
*/

Subtask #1

5.0 / 5.0

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

Subtask #2

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	2 ms	896 KB	Output is correct
6	Correct	3 ms	896 KB	Output is correct
7	Correct	3 ms	1024 KB	Output is correct
8	Correct	3 ms	1024 KB	Output is correct
9	Correct	2 ms	1024 KB	Output is correct
10	Correct	3 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	3 ms	896 KB	Output is correct
13	Correct	3 ms	1024 KB	Output is correct
14	Correct	2 ms	896 KB	Output is correct
15	Correct	2 ms	896 KB	Output is correct
16	Correct	3 ms	896 KB	Output is correct
17	Correct	3 ms	896 KB	Output is correct
18	Correct	9 ms	8576 KB	Output is correct
19	Correct	9 ms	8576 KB	Output is correct
20	Correct	10 ms	8576 KB	Output is correct
21	Correct	8 ms	8576 KB	Output is correct
22	Correct	8 ms	8576 KB	Output is correct
23	Correct	10 ms	8576 KB	Output is correct
24	Correct	10 ms	8704 KB	Output is correct
25	Correct	10 ms	8576 KB	Output is correct
26	Correct	9 ms	8704 KB	Output is correct
27	Correct	8 ms	8576 KB	Output is correct
28	Correct	9 ms	8576 KB	Output is correct
29	Correct	10 ms	8624 KB	Output is correct
30	Correct	10 ms	8576 KB	Output is correct
31	Correct	10 ms	8644 KB	Output is correct
32	Correct	9 ms	8704 KB	Output is correct
33	Correct	8 ms	8320 KB	Output is correct
34	Correct	8 ms	8320 KB	Output is correct
35	Correct	8 ms	8064 KB	Output is correct
36	Correct	8 ms	8320 KB	Output is correct
37	Correct	8 ms	7936 KB	Output is correct
38	Correct	8 ms	8576 KB	Output is correct
39	Correct	8 ms	8576 KB	Output is correct
40	Correct	8 ms	8320 KB	Output is correct
41	Correct	9 ms	8576 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	462 ms	380800 KB	Output is correct
3	Correct	398 ms	378872 KB	Output is correct
4	Correct	402 ms	380792 KB	Output is correct
5	Correct	384 ms	380812 KB	Output is correct
6	Correct	397 ms	380836 KB	Output is correct
7	Correct	380 ms	378920 KB	Output is correct
8	Correct	383 ms	378876 KB	Output is correct
9	Correct	375 ms	377108 KB	Output is correct
10	Correct	382 ms	380792 KB	Output is correct
11	Correct	397 ms	380792 KB	Output is correct
12	Correct	96 ms	99832 KB	Output is correct
13	Correct	182 ms	177528 KB	Output is correct
14	Correct	264 ms	258424 KB	Output is correct
15	Correct	378 ms	380792 KB	Output is correct
16	Correct	401 ms	380828 KB	Output is correct

Subtask #4

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	2 ms	896 KB	Output is correct
6	Correct	3 ms	896 KB	Output is correct
7	Correct	3 ms	1024 KB	Output is correct
8	Correct	3 ms	1024 KB	Output is correct
9	Correct	2 ms	1024 KB	Output is correct
10	Correct	3 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	3 ms	896 KB	Output is correct
13	Correct	3 ms	1024 KB	Output is correct
14	Correct	2 ms	896 KB	Output is correct
15	Correct	2 ms	896 KB	Output is correct
16	Correct	3 ms	896 KB	Output is correct
17	Correct	3 ms	896 KB	Output is correct
18	Correct	9 ms	8576 KB	Output is correct
19	Correct	9 ms	8576 KB	Output is correct
20	Correct	10 ms	8576 KB	Output is correct
21	Correct	8 ms	8576 KB	Output is correct
22	Correct	8 ms	8576 KB	Output is correct
23	Correct	10 ms	8576 KB	Output is correct
24	Correct	10 ms	8704 KB	Output is correct
25	Correct	10 ms	8576 KB	Output is correct
26	Correct	9 ms	8704 KB	Output is correct
27	Correct	8 ms	8576 KB	Output is correct
28	Correct	9 ms	8576 KB	Output is correct
29	Correct	10 ms	8624 KB	Output is correct
30	Correct	10 ms	8576 KB	Output is correct
31	Correct	10 ms	8644 KB	Output is correct
32	Correct	9 ms	8704 KB	Output is correct
33	Correct	8 ms	8320 KB	Output is correct
34	Correct	8 ms	8320 KB	Output is correct
35	Correct	8 ms	8064 KB	Output is correct
36	Correct	8 ms	8320 KB	Output is correct
37	Correct	8 ms	7936 KB	Output is correct
38	Correct	8 ms	8576 KB	Output is correct
39	Correct	8 ms	8576 KB	Output is correct
40	Correct	8 ms	8320 KB	Output is correct
41	Correct	9 ms	8576 KB	Output is correct
42	Correct	2 ms	384 KB	Output is correct
43	Correct	462 ms	380800 KB	Output is correct
44	Correct	398 ms	378872 KB	Output is correct
45	Correct	402 ms	380792 KB	Output is correct
46	Correct	384 ms	380812 KB	Output is correct
47	Correct	397 ms	380836 KB	Output is correct
48	Correct	380 ms	378920 KB	Output is correct
49	Correct	383 ms	378876 KB	Output is correct
50	Correct	375 ms	377108 KB	Output is correct
51	Correct	382 ms	380792 KB	Output is correct
52	Correct	397 ms	380792 KB	Output is correct
53	Correct	96 ms	99832 KB	Output is correct
54	Correct	182 ms	177528 KB	Output is correct
55	Correct	264 ms	258424 KB	Output is correct
56	Correct	378 ms	380792 KB	Output is correct
57	Correct	401 ms	380828 KB	Output is correct
58	Correct	405 ms	380776 KB	Output is correct
59	Correct	419 ms	380748 KB	Output is correct
60	Correct	403 ms	376952 KB	Output is correct
61	Correct	413 ms	379000 KB	Output is correct
62	Correct	397 ms	380792 KB	Output is correct
63	Correct	392 ms	380888 KB	Output is correct
64	Correct	395 ms	380956 KB	Output is correct
65	Correct	397 ms	379000 KB	Output is correct
66	Correct	390 ms	375156 KB	Output is correct
67	Correct	422 ms	380792 KB	Output is correct
68	Correct	434 ms	378824 KB	Output is correct
69	Correct	398 ms	380892 KB	Output is correct
70	Correct	424 ms	380876 KB	Output is correct
71	Correct	400 ms	378948 KB	Output is correct
72	Correct	390 ms	378868 KB	Output is correct
73	Correct	374 ms	380920 KB	Output is correct