Submission #370375

#	Time	Username	Problem	Language	Result	Execution time	Memory
370375		shivensinha4	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	451 ms	757612 KiB

joi2019_ho_t3

#pragma GCC optimize ("unroll-loops")
#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 cpos[3];
	int nums[n], dp[n+1][n+1][n+1][3], t[3], ct[3], cost[3], pref[n][3];
	memset(dp, 0x3f, sizeof(dp)); memset(pref, 0, sizeof(pref));
	
	for_(i, 0, n) {
		if (s[i] == 'G') nums[i] = 1;
		else if (s[i] == 'Y') nums[i] = 2;
		else nums[i] = 0;
		
		cpos[nums[i]].push_back(i);
		pref[i][nums[i]]++;
	}
	
	for_(i, 1, n) for_(j, 0, 3) pref[i][j] += pref[i-1][j];
	
	const int INF = 1e9;
	for_(i, 0, 3) ct[i] = cpos[i].size();
	
	int ans, pos;
	for (int i = n; i >= 0; i--) for (t[0] = 0; t[0] <= min(ct[0], i); t[0]++) for (t[1] = 0; t[1] <= min(ct[1], i-t[0]); t[1]++) {
		t[2] = i-t[0]-t[1];
		if (t[2] > ct[2]) continue;
		for_(c, 0, 3) {
			if (t[c] < ct[c]) {
				pos = cpos[c][t[c]];
				cost[c] = pos - (pos > 0 ? min(pref[pos-1][0], t[0]) + min(pref[pos-1][1], t[1]) + min(pref[pos-1][2], t[2]) : 0);
			} else cost[c] = -1;
		}
		
		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] + cost[c]);
			}
			
			dp[i][t[0]][t[1]][last] = ans;
		}
	}
	
	ans = min({dp[0][0][0][1], dp[0][0][0][0]});
	
	cout << (ans >= INF ? -1 : ans) << endl;
	
	return 0;
}

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