Submission #370360

#TimeUsernameProblemLanguageResultExecution timeMemory
370360shivensinha4Growing Vegetable is Fun 3 (JOI19_ho_t3)C++17
15 / 100
474 ms757628 KiB
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; string s; cin >> n >> s;
	vi nums(n);
	vector<vi> cpos(3);
	for_(i, 0, n) {
		if (s[i] == 'G') nums[i] = 1;
		else if (s[i] == 'Y') nums[i] = 2;
		cpos[nums[i]].push_back(i);
	}
	
	const int INF = 1e9;
	int dp[n+1][n+1][n+1][3], t[3], ct[3];
	memset(dp, 0x3f, sizeof(dp));
	
	for_(i, 0, 3) ct[i] = cpos[i].size();
	
	int ans;
	for (int i = n; i >= 0; i--) for (t[0] = 0; t[0] < min(ct[0], i) + 1; t[0]++) for (t[1] = 0; t[1] < min(ct[1], i-t[0]) + 1; t[1]++) {
		t[2] = i-t[0]-t[1];
		if (t[2] > ct[2]) continue;
		for_(last, 0, 3) {
			ans = INF;
			if (i == n) {
				ans = (t[0] == ct[0] and t[1] == ct[1] and t[2] == ct[2]) ? 0 : INF;
			}
			else for_(c, 0, 3) if (c != last and ct[c] > t[c]) {
				ans = min(ans, dp[i+1][t[0]+(c==0)][t[1]+(c==1)][c] + max(i, cpos[c][t[c]]) - i);
//				if (i == 2 and t[0] == 1 and t[1] == 1 and last == 1 and dp[i+1][t[0]+(c==0)][t[1]+(c==1)][c] + max(i, cpos[c][t[c]]) - i == 0)
//					cout << "..." << i+1 << " " << (t[0]+(c==0)) << " " << (t[1]+(c==1)) << " " << c << endl;
			}
			
			dp[i][t[0]][t[1]][last] = ans;
		}
	}
	
//	cout << dp[0][0][0][1] << " " << dp[1][1][0][0] << " " << dp[2][1][1][1] << " " << dp[3][2][1][0] << endl;
	ans = min({dp[0][0][0][1], dp[0][0][0][0], dp[0][0][0][2]});
	
	cout << (ans >= INF ? -1 : ans) << endl;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...