Submission #929090

#	Time	Username	Problem	Language	Result	Execution time	Memory
929090		siewjh	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	302 ms	780652 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 405;
int memo[MAXN][MAXN][MAXN][3], pos[3][MAXN], cnt[3], pref[3][MAXN];
const int inf = 1e9 + 7;
int dp(int c0, int c1, int c2, int fr){
	if (c0 == 0 && c1 == 0 && c2 == 0) return 0;
	if (memo[c0][c1][c2][fr] != -1) return memo[c0][c1][c2][fr];
	int ans = inf;
	if (fr == 0){
		if (c0 != 0){
			int ipos = pos[0][c0], swps = ipos + max(c1 - pref[1][ipos], 0) + max(c2 - pref[2][ipos], 0) - (c0 + c1 + c2);
			ans = min(ans, min(dp(c0 - 1, c1, c2, 1), dp(c0 - 1, c1, c2, 2)) + swps);
		}
	}
	else if (fr == 1){
		if (c1 != 0){
			int ipos = pos[1][c1], swps = ipos + max(c0 - pref[0][ipos], 0) + max(c2 - pref[2][ipos], 0) - (c0 + c1 + c2);
			ans = min(ans, min(dp(c0, c1 - 1, c2, 0), dp(c0, c1 - 1, c2, 2)) + swps);
		}
	}
	else{
		if (c2 != 0){
			int ipos = pos[2][c2], swps = ipos + max(c0 - pref[0][ipos], 0) + max(c1 - pref[1][ipos], 0) - (c0 + c1 + c2);
			ans = min(ans, min(dp(c0, c1, c2 - 1, 0), dp(c0, c1, c2 - 1, 1)) + swps);
		}
	}
	return memo[c0][c1][c2][fr] = ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	for (int i = 1; i <= nums; i++){
		char ch; cin >> ch;
		int v;
		if (ch == 'R') v = 0;
		else if (ch == 'Y') v = 1;
		else v = 2;
		cnt[v]++;
		pos[v][cnt[v]] = i;
		for (int j = 0; j < 3; j++) pref[j][i] = pref[j][i - 1];
		pref[v][i]++;
	}
	memset(memo, -1, sizeof(memo));
	int ans = inf;
	for (int j = 0; j < 3; j++) ans = min(ans, dp(cnt[0], cnt[1], cnt[2], j));
	cout << ((ans == inf) ? -1 : ans);
}

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