제출 #370359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
370359		shivensinha4	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	393 ms	757740 KiB

joi2019_ho_t3

#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);
			}
			
			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: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25