Submission #679645

#	Time	Username	Problem	Language	Result	Execution time	Memory
679645		ethening	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	189 ms	134816 KiB

joi2019_ho_t3

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	string s;
	cin >> n >> s;
	vector<int> pr(n + 1), pg(n + 1), py(n + 1);
	vector<int> vr, vg, vy;
	for (int i = 1; i <= n; i++) {
		pr[i] = pr[i - 1];
		pg[i] = pg[i - 1];
		py[i] = py[i - 1];
		if (s[i - 1] == 'R') {
			++pr[i];
			vr.push_back(i);
		}
		else if (s[i - 1] == 'G') {
			++pg[i];
			vg.push_back(i);
		}
		else if (s[i - 1] == 'Y') {
			++py[i];
			vy.push_back(i);
		}
	}
	int nr = (int)vr.size();
	int ng = (int)vg.size();
	int ny = (int)vy.size();
	vector dp(nr + 1, vector(ng + 1, vector(ny + 1, vector(3, 1000000000))));
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for (int i = 0; i <= nr; i++) {
		for (int j = 0; j <= ng; j++) {
			for (int k = 0; k <= ny; k++) {
				if (i > 0) {
					int pos = vr[i - 1];
					dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k][1] + abs(pg[pos] - j) + abs(py[pos] - k));
					dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k][2] + abs(pg[pos] - j) + abs(py[pos] - k));
				}
				if (j > 0) {
					int pos = vg[j - 1];
					dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j - 1][k][0] + abs(pr[pos] - i) + abs(py[pos] - k));
					dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j - 1][k][2] + abs(pr[pos] - i) + abs(py[pos] - k));
				}
				if (k > 0) {
					int pos = vy[k - 1];
					dp[i][j][k][2] = min(dp[i][j][k][2], dp[i][j][k - 1][0] + abs(pr[pos] - i) + abs(pg[pos] - j));
					dp[i][j][k][2] = min(dp[i][j][k][2], dp[i][j][k - 1][1] + abs(pr[pos] - i) + abs(pg[pos] - j));
				}
				// for (int l = 0; l < 3; l++) {
				// 	cout << i << " " << j << " " << k << " " << l << " : " << dp[i][j][k][l] << endl;
				// }
			}
		}
	}
	int ans = min(dp[nr][ng][ny][0], min(dp[nr][ng][ny][1], dp[nr][ng][ny][2]));
	cout << ((ans >= 10000000) ? -1 : ans / 2) << endl;
}

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