Submission #820210

#	Time	Username	Problem	Language	Result	Execution time	Memory
820210		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	381 ms	200428 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
 
array<int, 255> colorCode;
const int iINF	= 1e9;
const int maxN	= 423;
 
int N, cnt[3], color[maxN], pos[3][maxN], pf[3][maxN];
int dp[maxN][maxN][maxN][3];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	colorCode['R'] = 0;
	colorCode['G'] = 1;
	colorCode['Y'] = 2;
 
	cin >> N;
	char buf;
	for (int i = 1; i <= N; i++) {
		cin >> buf;
		color[i] = colorCode[buf];
	}
 
	#define R	cnt[0]
	#define G	cnt[1]
	#define Y	cnt[2]
 
	#define r	lpos[0]
	#define g	lpos[1]
	#define y	lpos[2]
	
	for (int i = 1; i <= N; i++) {
		pos[color[i]][++cnt[color[i]]] = i;
		for (int j = 0; j <= 2; j++) {
			pf[j][i] = pf[j][i-1] + (color[i] == j);
		}
	}
 
	int bound	= (N + 1) / 2;
	if (max({R, G, Y}) > bound) {
		cout << -1 << '\n';
		return 0;
	}
 
	// dp[r][g][y][lst] = number of swaps to the left that must be done
	// to get r red, g green, and y yellow with last color lst
	array<int, 3> lpos;
	for (int n = 1; n <= N; n++) {
		for (r = 0; r <= bound; r++) {
			for (g = 0; g <= min(n-r, bound); g++) {
				y = n-r-g;
				for (int lst = 0; lst <= 2; lst++) {
					if (!lpos[lst]) {
						dp[r][g][y][lst] = iINF;
						continue;
					}
 
					int prv = iINF;
					lpos[lst]--;
					for (int plst = 0; plst <= 2; plst++) {
						if (plst == lst) continue;
						prv = min(prv, dp[r][g][y][plst]);
					}
					lpos[lst]++;
 
					int swaps = 0;
					for (int i = 0; i <= 2; i++) {
						if (i == lst) continue;
						swaps += max(0, pf[i][pos[lst][lpos[lst]]] - lpos[i]);
					}
 
					dp[r][g][y][lst] = min(iINF, prv + swaps);
				}
			}
		}
	}
 
	int ans = iINF;
	for (int lst = 0; lst <= 2; lst++) ans = min(ans, dp[R][G][Y][lst]);
	if (ans == iINF) ans = -1;
	cout << ans << '\n';
}

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