Submission #1357726

#TimeUsernameProblemLanguageResultExecution timeMemory
1357726silverwolfGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
41 ms28724 KiB
/*
tags: usaco | codeforces | centroid_decomposition 
*/
 
#include <bits/stdc++.h>
using namespace std;
using namespace std::complex_literals;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
 
#define ll long long
#define mask(i) (1 << (i))
#define bit(x, i)  (((x) >> (i)) & 1)
#define onbit(x, i) ((x) = (x) | mask(i))
#define offbit(x, i) ((x) = (x) & (~mask(i)))
#define pcount(i) __builtin_popcount(i)
#define bctz(i) __builtin_ctz(i)
#define all(v) v.begin(), v.end()
#define all1(v) v.begin()+1, v.end()
#define sz(v) (int)v.size()
#define sqr(x) ((x) * (x))
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FORD(i,l,r) for(int i=(l);i>=(r);i--)
#define REP(i, r) for(int i=0;i<(r);i++)
#define BITSET(size, x) std::bitset<size + 1>(x).to_string().c_str()
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define complex complex<long double>
#define ite std::vector<int>::iterator
// #define int ll
template <class T> bool minimize(T& x,T y) {
    if (x > y) x = y; else return 0; return 1;
}
template <class T> bool maximize(T& x,T y) {
    if (x < y) x = y; else return 0; return 1;
}
const int INF = 1e9 + 2;
const int MAX = 402;
int p[3][MAX];
vi t[3];
inline void solve()
{
	int n;
	string s;
	cin >> n;
	cin >> s;
	int cr = 0;
	int cg = 0;
	int cy = 0;
	for(int i = 0; i < n; i++) {
		p[0][i + 1] = p[0][i];
		p[1][i + 1] = p[1][i];
		p[2][i + 1] = p[2][i];
		if(s[i] == 'R') {
			p[0][i+1]++;
			t[0].push_back(i);
			cr++;
		}
		if(s[i] == 'G') {
			p[1][i+1]++;
			t[1].push_back(i);
			cg++;
		}
		if(s[i] == 'Y'){
			p[2][i+1]++;
			t[2].push_back(i);
			cy++;
		}
	}
	if(max(cr, max(cg,cy)) > n / 2 + (n & 1)) {
		cout << -1 << '\n';
		return;
	} 
	int dp[3][cr + 1][cg + 1][cy + 1];
	for(int i = 0; i < 3;i++) {
		for(int j = 0; j <= cr;j++) {
			for(int k = 0; k <= cg;k++) {
				for(int l = 0; l <= cy; l++) {
					dp[i][j][k][l] = INF;
				}
			}
		}
	}
	if(cr > 0) dp[0][1][0][0] = 0;
	if(cg > 0) dp[1][0][1][0] = 0;
	if(cy > 0) dp[2][0][0][1] = 0;
	//R : 0; G : 1; Y : 2
	for(int i = 0; i <= cr;i++) {
		for(int j = 0; j <= cg; j++) {
			for(int k = 0; k <= cy; k++) {
				if(i + j + k < 2) continue;
				if(i != 0) {
					int cnt = max(0, j - p[1][t[0][i - 1]]) + max(0, k - p[2][t[0][i - 1]]);
					dp[0][i][j][k] = min(dp[1][i - 1][j][k], dp[2][i - 1][j][k]) + cnt;
				}
				if(j != 0) {
					int cnt = max(0, i - p[0][t[1][j - 1]]) + max(0, k - p[2][t[1][j - 1]]);
					dp[1][i][j][k] = min(dp[0][i][j - 1][k], dp[2][i][j - 1][k]) + cnt;
				}
				if(k != 0) {
					int cnt = max(0, i - p[0][t[2][k - 1]]) + max(0, j - p[1][t[2][k - 1]]);
					dp[2][i][j][k] = min(dp[0][i][j][k - 1], dp[1][i][j][k - 1]) + cnt;
				}
			}
		}
	}
	int ans = min(dp[0][cr][cg][cy], min(dp[1][cr][cg][cy], dp[2][cr][cg][cy]));
	cout << ans << '\n';
}
 
int main() {
	#ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout); 
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	solve();
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...