Submission #914832

#	Time	Username	Problem	Language	Result	Execution time	Memory
914832		happypotato	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	368 ms	761424 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
unordered_map<char, int> conv = {{'R', 0}, {'G', 1}, {'Y', 2}};
const int mxN = 402;
int dp[mxN][mxN][mxN][3];
int a[mxN];
vector<int> v[3];
int pref[3][mxN];
int suff[3][mxN];
int n;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n;
	string temp; cin >> temp;
	for (int i = 1; i <= n; i++) a[i] = conv[temp[i - 1]];

	for (int i = 0; i < 3; i++) {
		v[i] = {-1};
		pref[i][0] = 0;
		for (int j = 1; j <= n; j++) {
			pref[i][j] = pref[i][j - 1];
			if (a[j] == i) {
				pref[i][j]++; v[i].pb(j);
			}
		}
		suff[i][n + 1] = 0;
		for (int j = n; j >= 1; j--) {
			suff[i][j] = suff[i][j + 1];
			if (a[j] == i) {
				suff[i][j]++;
			}
		}
	}

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				for (int l = 0; l < 3; l++) {
					dp[i][j][k][l] = 1e8;
				}
			}
		}
	}

	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for (int a = 0; a <= pref[0][n]; a++) {
		for (int b = 0; b <= pref[1][n]; b++) {
			for (int c = 0; c <= pref[2][n]; c++) {
				if (a + b + c == 0) continue;
				if (a) {
					dp[a][b][c][0] = min(dp[a - 1][b][c][1], dp[a - 1][b][c][2]) + max(b - pref[1][v[0][a]], 0) + max(c - pref[2][v[0][a]], 0);
				}
				if (b) {
					dp[a][b][c][1] = min(dp[a][b - 1][c][0], dp[a][b - 1][c][2]) + max(a - pref[0][v[1][b]], 0) + max(c - pref[2][v[1][b]], 0);
				}
				if (c) {
					dp[a][b][c][2] = min(dp[a][b][c - 1][0], dp[a][b][c - 1][1]) + max(a - pref[0][v[2][c]], 0) + max(b - pref[1][v[2][c]], 0);
				}
				// cerr << a << ' ' << b << ' ' << c << ":\n";
				// for (int i = 0; i < 3; i++) cerr << dp[a][b][c][i] << ' ';
				// cerr << '\n';
			}
		}
	}

	int ans = 1e8;
	for (int i = 0; i < 3; i++) ans = min(ans, dp[pref[0][n]][pref[1][n]][pref[2][n]][i]);
	cout << (ans == 1e8 ? -1 : ans) << '\n';
}

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