Submission #1134014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134014		am_aadvik	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	115 ms	194788 KiB

joi2019_ho_t3

#include <iostream>
using namespace std;

int dp[3][405][405][405]; //lst, cnt_r, cnt_g, idx
int pos[3][405], cnt[3], pre[3][405]; //RGY
int32_t main() {
	int n; cin >> n;
	string s; cin >> s; s = " " + s;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j) {
			pre[j][i] = pre[j][i - 1];
			if (s[i] == "RGY"[j])
				++cnt[j], pos[j][cnt[j]] = i, pre[j][i]++;
		}
	}

	for (int i = 0; i < 3; ++i)
		dp[i][0][0][0] = 0; //base case

	for (int cr = 0; cr <= cnt[0]; ++cr)
		for (int cg = 0; cg <= cnt[1]; ++cg)
			for (int i = 1; i <= n; ++i) {
				int cy = i - cg - cr;
				if ((cy < 0) || (cy > cnt[2])) continue;
				if (cr > 0)
					dp[0][cr][cg][i] = min(dp[1][cr - 1][cg][i - 1], dp[2][cr - 1][cg][i - 1])
					+ cg - min(cg, pre[1][pos[0][cr]]) + cy - min(cy, pre[2][pos[0][cr]]);
				else dp[0][cr][cg][i] = 1e9;

				if (cg > 0)
					dp[1][cr][cg][i] = min(dp[0][cr][cg - 1][i - 1], dp[2][cr][cg - 1][i - 1])
					+ cr - min(cr, pre[0][pos[1][cg]]) + cy - min(cy, pre[2][pos[1][cg]]);
				else dp[1][cr][cg][i] = 1e9;

				if (cy > 0)
					dp[2][cr][cg][i] = min(dp[1][cr][cg][i - 1], dp[0][cr][cg][i - 1])
					+ cg - min(cg, pre[1][pos[2][cy]]) + cr - min(cr, pre[0][pos[2][cy]]);
				else dp[2][cr][cg][i] = 1e9;
			}

	int ans = 1e9;
	for (int i = 0; i < 3; ++i)
		ans = min(ans, dp[i][cnt[0]][cnt[1]][n]);
	cout << ((ans == 1e9) ? -1 : ans);
}

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