Submission #817671

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

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

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);
		}
	}

	// for (int j = 0; j <= 2; j++) {
	// 	for (int i = 1; i <= N; i++) cout << pos[j][i] << ' ';
	// 	cout << '\n';
	// 	for (int i = 1; i <= N; i++) cout << pf[j][i] << ' ';
	// 	cout << '\n';
	// 	cout << '\n';
	// }

	// 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 <= n; r++) {
			for (g = 0; g <= n-r; 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);
					// fprintf(stderr, "dp[%d][%d][%d][%d] = %d\n", r, g, y, lst, dp[r][g][y][lst]);
				}
			}
		}
	}

	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