Submission #706488

#	Time	Username	Problem	Language	Result	Execution time	Memory
706488		rainboy	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C11	100 / 100	39 ms	28724 KiB

joi2019_ho_t3

#include <stdio.h>
#include <string.h>

#define N	400
#define M	(1 << 23)
#define INF	0x3f3f3f3f

int abs_(int a) { return a > 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }

int main() {
	static char cc[N + 1];
	static int kk[3][3][N], dp[M];
	int n, i, nr, ng, ny, kr, kg, ky, c, u, v, x, ans;

	scanf("%d%s", &n, cc);
	nr = ng = ny = 0;
	for (i = 0; i < n; i++)
		if (cc[i] == 'R')
			kk[0][1][nr] = ng, kk[0][2][nr] = ny, nr++;
		else if (cc[i] == 'G')
			kk[1][2][ng] = ny, kk[1][0][ng] = nr, ng++;
		else
			kk[2][0][ny] = nr, kk[2][1][ny] = ng, ny++;
	memset(dp, 0x3f, (nr + 1) * (ng + 1) * (ny + 1) * 3 * sizeof *dp);
	for (c = 0; c < 3; c++) {
		u = ((0 * (ng + 1) + 0) * (ny + 1) + 0) * 3 + c;
		dp[u] = 0;
	}
	for (kr = 0; kr <= nr; kr++)
		for (kg = 0; kg <= ng; kg++)
			for (ky = 0; ky <= ny; ky++)
				for (c = 0; c < 3; c++) {
					u = ((kr * (ng + 1) + kg) * (ny + 1) + ky) * 3 + c, x = dp[u];
					if (x == INF)
						continue;
					if (kr < nr && c != 0) {
						v = (((kr + 1) * (ng + 1) + kg) * (ny + 1) + ky) * 3 + 0;
						dp[v] = min(dp[v], x + abs_(kk[0][1][kr] - kg) + abs_(kk[0][2][kr] - ky));
					}
					if (kg < ng && c != 1) {
						v = ((kr * (ng + 1) + (kg + 1)) * (ny + 1) + ky) * 3 + 1;
						dp[v] = min(dp[v], x + abs_(kk[1][2][kg] - ky) + abs_(kk[1][0][kg] - kr));
					}
					if (ky < ny && c != 2) {
						v = ((kr * (ng + 1) + kg) * (ny + 1) + (ky + 1)) * 3 + 2;
						dp[v] = min(dp[v], x + abs_(kk[2][0][ky] - kr) + abs_(kk[2][1][ky] - kg));
					}
				}
	ans = INF;
	for (c = 0; c < 3; c++) {
		u = ((nr * (ng + 1) + ng) * (ny + 1) + ny) * 3 + c;
		if (dp[u] != INF)
			ans = min(ans, dp[u] / 2);
	}
	if (ans == INF)
		ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.c: In function 'main':
joi2019_ho_t3.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~

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