Submission #755661

#	Time	Username	Problem	Language	Result	Execution time	Memory
755661		MISM06	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	76 ms	98068 KiB

joi2019_ho_t3

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef short int it;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 400 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1000;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;

it dp[N][N][N][3], n, a[N], cnt[N][3], A, B, C;
string s;
vector < it > p[3];
inline it give (it l, it r, it t) {
	if (l > r) return 0;
	return cnt[r][t] - cnt[l - 1][t];
}

void solve () {

	cin >> n;
	cin >> s;
	s = '.' + s; p[0].pb(0); p[1].pb(0); p[2].pb(0);
	for (int i = 1; i <= n; i++) {
		if (s[i] == 'R') {
			p[0].pb(i); a[i] = 0; ++cnt[i][0];
		} else if (s[i] == 'G') {
			p[1].pb(i); a[i] = 1; ++cnt[i][1];
		} else {
			p[2].pb(i); a[i] = 2; ++cnt[i][2];
		}
		cnt[i][0] += cnt[i - 1][0];
		cnt[i][1] += cnt[i - 1][1];
		cnt[i][2] += cnt[i - 1][2];
	}
	A = p[0].sze - 1;
	B = p[1].sze - 1;
	C = p[2].sze - 1;
	it c[3]; c[0] = 0; c[1] = 0; c[2] = 0;
	for (; c[0] <= A; c[0]++) {
		for (c[1] = 0; c[1] <= B; c[1]++) {
			for (c[2] = 0; c[2] <= C; c[2]++) {
				if (c[0] == 0 && c[1] == 0 && c[2] == 0) continue;
				for (it t = 0; t < 3; t++) {
					if (c[t] == 0) {
						dp[c[0]][c[1]][c[2]][t] = 20000;
						continue;
					}

					it m = max({p[0][c[0]], p[1][c[1]], p[2][c[2]]});
					it l = p[t][c[t]];
					it len = m - l;
					len -= give(l + 1, m, t);
					l = max(p[t][c[t]], p[(t + 1) % 3][c[(t + 1) % 3]]);
					len -= give(l + 1, m, (t + 1) % 3);
					l = max(p[t][c[t]], p[(t + 2) % 3][c[(t + 2) % 3]]);
					len -= give(l + 1, m, (t + 2) % 3);

					if (t == 0) dp[c[0]][c[1]][c[2]][t] = len + min(dp[c[0] - 1][c[1]][c[2]][(t + 1) % 3], dp[c[0] - 1][c[1]][c[2]][(t + 2) % 3]);
					else if (t == 1) dp[c[0]][c[1]][c[2]][t] = len + min(dp[c[0]][c[1] - 1][c[2]][(t + 1) % 3], dp[c[0]][c[1] - 1][c[2]][(t + 2) % 3]);
					else dp[c[0]][c[1]][c[2]][t] = len + min(dp[c[0]][c[1]][c[2] - 1][(t + 1) % 3], dp[c[0]][c[1]][c[2] - 1][(t + 2) % 3]);
				}
			}
		}
	}
	if (min({dp[A][B][C][0], dp[A][B][C][1], dp[A][B][C][2]}) >= 20000) cout << -1 << '\n';
	else cout << min({dp[A][B][C][0], dp[A][B][C][1], dp[A][B][C][2]}) << '\n';

}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//shrek will AC this;

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