Submission #914833

#	Time	Username	Problem	Language	Result	Execution time	Memory
914833		happypotato	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	321 ms	761232 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 ps[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};
		ps[i][0] = 0;
		for (int j = 1; j <= n; j++) {
			ps[i][j] = ps[i][j - 1];
			if (a[j] == i) {
				ps[i][j]++; v[i].pb(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 <= ps[0][n]; a++) {
		for (int b = 0; b <= ps[1][n]; b++) {
			for (int c = 0; c <= ps[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 - ps[1][v[0][a]], 0) + max(c - ps[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 - ps[0][v[1][b]], 0) + max(c - ps[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 - ps[0][v[2][c]], 0) + max(b - ps[1][v[2][c]], 0);
				}
			}
		}
	}

	int ans = 1e8;
	for (int i = 0; i < 3; i++) ans = min(ans, dp[ps[0][n]][ps[1][n]][ps[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