Submission #1168464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168464		yellowtoad	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	178 ms	8164 KiB

joi2019_ho_t3

#include <iostream>
#define f first
#define s second
using namespace std;

long long n, a[410], dp[410][410][3], tmp[410][410][3], ps[3][410], b[3][410], cnt[3]; // R, G
string s;

long long sum(int x, int y, int z, int id) {
	pair<int,int> i, j, k;
	int res = 0;
	if (id == 0) i = {b[0][x],0}, j = min(make_pair(b[1][y],1),make_pair(b[2][z],2)), k = max(make_pair(b[1][y],1),make_pair(b[2][z],2));
	else if (id == 1) i = {b[1][y],1}, j = min(make_pair(b[0][x],0),make_pair(b[2][z],2)), k = max(make_pair(b[0][x],0),make_pair(b[2][z],2));
	else i = {b[2][z],2}, j = min(make_pair(b[0][x],0),make_pair(b[1][y],1)), k = max(make_pair(b[0][x],0),make_pair(b[1][y],1));
	if (i > k) res += i.f-k.f-ps[i.s][i.f]+ps[i.s][k.f];
	if (i > j) res += ps[j.s][k.f]-ps[j.s][j.f];
	return res;
}

int main() {
	cin >> n >> s;
	for (int i = 1; i <= n; i++) {
		if (s[i-1] == 'R') a[i] = 0;
		else if (s[i-1] == 'G') a[i] = 1;
		else a[i] = 2;
		b[a[i]][++cnt[a[i]]] = i;
		for (int j = 0; j <= 2; j++) ps[j][i] = ps[j][i-1];
		ps[a[i]][i]++;
	}
	for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) for (int l = 0; l <= 2; l++) dp[j][k][l] = 1e9;
	dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) for (int l = 0; l <= 2; l++) tmp[j][k][l] = 1e9;
		for (int x = 0; x <= cnt[0]; x++) {
			for (int y = 0; y <= cnt[1]; y++) {
				int z = i-x-y;
				if ((x+y > i) || (z > cnt[2])) continue;
				if (x) tmp[x][y][0] = min(dp[x-1][y][1]+sum(x,y,z,0),dp[x-1][y][2]+sum(x,y,z,0));
				if (y) tmp[x][y][1] = min(dp[x][y-1][0]+sum(x,y,z,1),dp[x][y-1][2]+sum(x,y,z,1));
				if (z) tmp[x][y][2] = min(dp[x][y][0]+sum(x,y,z,2),dp[x][y][1]+sum(x,y,z,2));
			}
		}
		for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) for (int l = 0; l <= 2; l++) dp[j][k][l] = tmp[j][k][l];
	}
	if (min(dp[cnt[0]][cnt[1]][0],min(dp[cnt[0]][cnt[1]][1],dp[cnt[0]][cnt[1]][2])) >= 1e9) cout << -1 << endl;
	else cout << min(dp[cnt[0]][cnt[1]][0],min(dp[cnt[0]][cnt[1]][1],dp[cnt[0]][cnt[1]][2])) << endl;
}

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