답안 #817664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817664	2023-08-09T14:49:52 Z	Zanite	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	500 ms	373084 KB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

array<int, 255> colorCode;
const int iINF	= 1e9;
const int maxN	= 401;

int N, cnt[3], color[maxN], pos[3][maxN], pf[3][maxN];
int dp[maxN][maxN][maxN][3];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	colorCode['R'] = 0;
	colorCode['G'] = 1;
	colorCode['Y'] = 2;

	cin >> N;
	char buf;
	for (int i = 1; i <= N; i++) {
		cin >> buf;
		color[i] = colorCode[buf];
	}

	#define R	cnt[0]
	#define G	cnt[1]
	#define Y	cnt[2]

	#define r	lpos[0]
	#define g	lpos[1]
	#define y	lpos[2]
	
	for (int i = 1; i <= N; i++) {
		pos[color[i]][++cnt[color[i]]] = i;
		for (int j = 0; j <= 2; j++) {
			pf[j][i] = pf[j][i-1] + (color[i] == j);
		}
	}

	// for (int j = 0; j <= 2; j++) {
	// 	for (int i = 1; i <= N; i++) cout << pos[j][i] << ' ';
	// 	cout << '\n';
	// 	for (int i = 1; i <= N; i++) cout << pf[j][i] << ' ';
	// 	cout << '\n';
	// 	cout << '\n';
	// }

	// dp[r][g][y][lst] = number of swaps to the left that must be done
	// to get r red, g green, and y yellow with last color lst
	array<int, 3> lpos;
	for (int n = 1; n <= N; n++) {
		for (r = 0; r <= n; r++) {
			for (g = 0; g <= n-r; g++) {
				y = n-r-g;
				for (int lst = 0; lst <= 2; lst++) {
					if (!lpos[lst]) {
						dp[r][g][y][lst] = iINF;
						continue;
					}

					int prv = iINF;
					lpos[lst]--;
					for (int plst = 0; plst <= 2; plst++) {
						if (plst == lst) continue;
						prv = min(prv, dp[r][g][y][plst]);
					}
					lpos[lst]++;

					int swaps = 0;
					for (int i = 0; i <= 2; i++) {
						if (i == lst) continue;
						swaps += max(0, pf[i][pos[lst][lpos[lst]]] - lpos[i]);
					}

					dp[r][g][y][lst] = min(iINF, prv + swaps);
					// fprintf(stderr, "dp[%d][%d][%d][%d] = %d\n", r, g, y, lst, dp[r][g][y][lst]);
				}
			}
		}
	}

	int ans = iINF;
	for (int lst = 0; lst <= 2; lst++) ans = min(ans, dp[R][G][Y][lst]);
	if (ans == iINF) ans = -1;
	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	852 KB	Output is correct
6	Correct	1 ms	852 KB	Output is correct
7	Correct	1 ms	852 KB	Output is correct
8	Correct	1 ms	852 KB	Output is correct
9	Correct	1 ms	852 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct
11	Correct	1 ms	872 KB	Output is correct
12	Correct	1 ms	852 KB	Output is correct
13	Correct	1 ms	852 KB	Output is correct
14	Correct	1 ms	852 KB	Output is correct
15	Correct	1 ms	852 KB	Output is correct
16	Correct	1 ms	852 KB	Output is correct
17	Correct	1 ms	852 KB	Output is correct

Subtask #2
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	852 KB	Output is correct
6	Correct	1 ms	852 KB	Output is correct
7	Correct	1 ms	852 KB	Output is correct
8	Correct	1 ms	852 KB	Output is correct
9	Correct	1 ms	852 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct
11	Correct	1 ms	872 KB	Output is correct
12	Correct	1 ms	852 KB	Output is correct
13	Correct	1 ms	852 KB	Output is correct
14	Correct	1 ms	852 KB	Output is correct
15	Correct	1 ms	852 KB	Output is correct
16	Correct	1 ms	852 KB	Output is correct
17	Correct	1 ms	852 KB	Output is correct
18	Correct	6 ms	8536 KB	Output is correct
19	Correct	4 ms	8532 KB	Output is correct
20	Correct	4 ms	8532 KB	Output is correct
21	Correct	4 ms	8564 KB	Output is correct
22	Correct	6 ms	8552 KB	Output is correct
23	Correct	5 ms	8532 KB	Output is correct
24	Correct	4 ms	8532 KB	Output is correct
25	Correct	4 ms	8532 KB	Output is correct
26	Correct	4 ms	8532 KB	Output is correct
27	Correct	4 ms	8532 KB	Output is correct
28	Correct	5 ms	8532 KB	Output is correct
29	Correct	5 ms	8532 KB	Output is correct
30	Correct	4 ms	8532 KB	Output is correct
31	Correct	4 ms	8496 KB	Output is correct
32	Correct	6 ms	8532 KB	Output is correct
33	Correct	4 ms	8276 KB	Output is correct
34	Correct	4 ms	8276 KB	Output is correct
35	Correct	5 ms	8020 KB	Output is correct
36	Correct	4 ms	8276 KB	Output is correct
37	Correct	4 ms	7628 KB	Output is correct
38	Correct	4 ms	8532 KB	Output is correct
39	Correct	4 ms	8528 KB	Output is correct
40	Correct	4 ms	8276 KB	Output is correct
41	Correct	4 ms	8532 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Execution timed out	685 ms	373084 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	852 KB	Output is correct
6	Correct	1 ms	852 KB	Output is correct
7	Correct	1 ms	852 KB	Output is correct
8	Correct	1 ms	852 KB	Output is correct
9	Correct	1 ms	852 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct
11	Correct	1 ms	872 KB	Output is correct
12	Correct	1 ms	852 KB	Output is correct
13	Correct	1 ms	852 KB	Output is correct
14	Correct	1 ms	852 KB	Output is correct
15	Correct	1 ms	852 KB	Output is correct
16	Correct	1 ms	852 KB	Output is correct
17	Correct	1 ms	852 KB	Output is correct
18	Correct	6 ms	8536 KB	Output is correct
19	Correct	4 ms	8532 KB	Output is correct
20	Correct	4 ms	8532 KB	Output is correct
21	Correct	4 ms	8564 KB	Output is correct
22	Correct	6 ms	8552 KB	Output is correct
23	Correct	5 ms	8532 KB	Output is correct
24	Correct	4 ms	8532 KB	Output is correct
25	Correct	4 ms	8532 KB	Output is correct
26	Correct	4 ms	8532 KB	Output is correct
27	Correct	4 ms	8532 KB	Output is correct
28	Correct	5 ms	8532 KB	Output is correct
29	Correct	5 ms	8532 KB	Output is correct
30	Correct	4 ms	8532 KB	Output is correct
31	Correct	4 ms	8496 KB	Output is correct
32	Correct	6 ms	8532 KB	Output is correct
33	Correct	4 ms	8276 KB	Output is correct
34	Correct	4 ms	8276 KB	Output is correct
35	Correct	5 ms	8020 KB	Output is correct
36	Correct	4 ms	8276 KB	Output is correct
37	Correct	4 ms	7628 KB	Output is correct
38	Correct	4 ms	8532 KB	Output is correct
39	Correct	4 ms	8528 KB	Output is correct
40	Correct	4 ms	8276 KB	Output is correct
41	Correct	4 ms	8532 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Execution timed out	685 ms	373084 KB	Time limit exceeded
44	Halted	0 ms	0 KB	-

답안 #817664

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 0 / 15.0

Subtask #4 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
0 / 15.0

Subtask #4
0 / 25.0