Submission #1274354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274354		kaiboy	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	51 ms	4208 KiB

joi2019_ho_t3

#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 400;
const int INF = 0x3f3f3f3f;

char cc[N + 1];
int dpr[N + 1][N + 1], dpg[N + 1][N + 1], dpy[N + 1][N + 1];
int dqr[N + 1][N + 1], dqg[N + 1][N + 1], dqy[N + 1][N + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> cc;
	int kr_ = 0, kg_ = 0, ky_ = 0;
	for (int i = 0; i < n; i++) {
		(cc[i] == 'R' ? kr_ : cc[i] == 'G' ? kg_ : ky_)++;
		for (int kr = 0; kr <= i + 1; kr++)
			for (int kg = 0; kr + kg <= i + 1; kg++)
				dqr[kr][kg] = dqg[kr][kg] = dqy[kr][kg] = INF;
		for (int kr = 0; kr <= i; kr++)
			for (int kg = 0; kr + kg <= i; kg++) {
				dqr[kr + 1][kg] = min(dqr[kr + 1][kg], min(dpg[kr][kg], dpy[kr][kg]));
				dqg[kr][kg + 1] = min(dqg[kr][kg + 1], min(dpr[kr][kg], dpy[kr][kg]));
				dqy[kr][kg] = min(dqy[kr][kg], min(dpr[kr][kg], dpg[kr][kg]));
			}
		for (int kr = 0; kr <= i + 1; kr++)
			for (int kg = 0; kr + kg <= i + 1; kg++) {
				int ky = i + 1 - kr - kg, a = max(kr_ - kr, 0) + max(kg_ - kg, 0) + max(ky_ - ky, 0);
				dpr[kr][kg] = dqr[kr][kg] + a, dpg[kr][kg] = dqg[kr][kg] + a, dpy[kr][kg] = dqy[kr][kg] + a;
			}
	}
	int ans = min(min(dpr[kr_][kg_], dpg[kr_][kg_]), dpy[kr_][kg_]);
	if (ans == INF)
		ans = -1;
	cout << ans << '\n';
	return 0;
}

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