Submission #1274360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274360		kaiboy	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	65 ms	4204 KiB

joi2019_ho_t3

#include <algorithm>
#include <iostream>

using namespace std;

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

char cc[N + 1];
int iir[N], iig[N], iiy[N], kkr[N + 1], kkg[N + 1], kky[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' ? iir[kr_++] : cc[i] == 'G' ? iig[kg_++] : iiy[ky_++]) = i;
		kkr[i] = kr_, kkg[i] = kg_, kky[i] = ky_;
	}
	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] + (kr && kr <= kr_ ? max(kg - kkg[iir[kr - 1]], 0) + max(ky - kky[iir[kr - 1]], 0) : 0);
				dpg[kr][kg] = dqg[kr][kg] + (kg && kg <= kg_ ? max(kr - kkr[iig[kg - 1]], 0) + max(ky - kky[iig[kg - 1]], 0) : 0);
				dpy[kr][kg] = dqy[kr][kg] + (ky && ky <= ky_ ? max(kr - kkr[iiy[ky - 1]], 0) + max(kg - kkg[iiy[ky - 1]], 0) : 0);
			}
	}
	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: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25