Submission #1274356

#TimeUsernameProblemLanguageResultExecution timeMemory
1274356kaiboyGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
15 / 100
56 ms4180 KiB
#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++) {
		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;
				dpr[kr][kg] = dqr[kr][kg] + max(kr - 1 - kr_, 0) + max(kg - kg_, 0) + max(ky - ky_, 0);
				dpg[kr][kg] = dqg[kr][kg] + max(kr - kr_, 0) + max(kg - 1 - kg_, 0) + max(ky - ky_, 0);
				dpy[kr][kg] = dqy[kr][kg] + max(kr - kr_, 0) + max(kg - kg_, 0) + max(ky - 1 - ky_, 0);
			}
		(cc[i] == 'R' ? kr_ : cc[i] == 'G' ? kg_ : ky_)++;
	}
	int ans = min(min(dpr[kr_][kg_], dpg[kr_][kg_]), dpy[kr_][kg_]);
	if (ans == INF)
		ans = -1;
	cout << ans << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...