Submission #319656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
319656	2020-11-06T03:09:15 Z	CodeTiger927	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	478 ms	780520 KB

joi2019_ho_t3

using namespace std;

#include <iostream>
#include <cstring>

#define MAXN 405

int dp[MAXN][MAXN][MAXN][3];
int N,prefix[MAXN][3],pos[MAXN][3],num[3];
string S;

inline int getNum(char c) {
	if(c == 'R') return 0;
	if(c == 'G') return 1;
	return 2;
}

int main() {
	cin >> N >> S;

	for(int i = 0;i < N;++i) {
		for(int j = 0;j < 3;++j) {
			prefix[i + 1][j] = prefix[i][j];
		}
		prefix[i + 1][getNum(S[i])]++;
		pos[++num[getNum(S[i])]][getNum(S[i])] = i + 1;
	}
	// 2139062143
	memset(dp,127,sizeof(dp));
	for(int i = 0;i < 3;++i) {
		dp[0][0][0][i] = 0;
	}
	for(int i = 0;i <= num[0];++i) {
		for(int j = 0;j <= num[1];++j) {
			for(int k = 0;k <= num[2];++k) {
				for(int pre = 0;pre < 3;++pre) {
					for(int next = 0;next < 3;++next) {
						if(next == pre || (next == 0 && i == num[0]) || (next == 1 && j == num[1]) || (next == 2 && k == num[2])) continue;
						int posA,posB,posC,other;
						if(pre == 0) {
							posA = pos[i][0];
							if(next == 1) {
								posB = pos[j + 1][1];
								posC = pos[k][2];
								other = 2;
							}else{
								posB = pos[k + 1][2];
								posC = pos[j][1];
								other = 1;
							}
						}else if(pre == 1) {
							posA = pos[j][1];
							if(next == 0) {
								posB = pos[i + 1][0];
								posC = pos[k][2];
								other = 2;
							}else{
								posB = pos[k + 1][2];
								posC = pos[i][0];
								other = 0;
							}
						}else{
							posA = pos[k][2];
							if(next == 1) {
								posB = pos[j + 1][1];
								posC = pos[i][0];
								other = 0;
							}else{
								posB = pos[i + 1][0];
								posC = pos[j][1];
								other = 1;
							}
						}
						int total = max(0,prefix[posB][pre] - prefix[posA][pre]) + max(0,prefix[posB][other] - prefix[posC][other]) + dp[i][j][k][pre];
						if(next == 0) {
							dp[i + 1][j][k][next] = min(dp[i + 1][j][k][next],total);
						}else if(next == 1) {
							dp[i][j + 1][k][next] = min(dp[i][j + 1][k][next],total);
						}else{
							dp[i][j][k + 1][next] = min(dp[i][j][k + 1][next],total);
						}
					}
				}
			}
		}
	}

	int ans = 2139062143;
	for(int i = 0;i < 3;++i) {
		ans = min(ans,dp[num[0]][num[1]][num[2]][i]);
	}
	cout << (ans == 2139062143 ? -1 : ans) << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	369 ms	780260 KB	Output is correct
2	Correct	367 ms	780388 KB	Output is correct
3	Correct	361 ms	780256 KB	Output is correct
4	Correct	360 ms	780388 KB	Output is correct
5	Correct	359 ms	780388 KB	Output is correct
6	Correct	366 ms	780300 KB	Output is correct
7	Correct	364 ms	780300 KB	Output is correct
8	Correct	363 ms	780388 KB	Output is correct
9	Correct	363 ms	780260 KB	Output is correct
10	Correct	367 ms	780260 KB	Output is correct
11	Correct	360 ms	780388 KB	Output is correct
12	Correct	367 ms	780388 KB	Output is correct
13	Correct	360 ms	780388 KB	Output is correct
14	Correct	362 ms	780392 KB	Output is correct
15	Correct	362 ms	780520 KB	Output is correct
16	Correct	360 ms	780392 KB	Output is correct
17	Correct	357 ms	780388 KB	Output is correct

Subtask #2
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	369 ms	780260 KB	Output is correct
2	Correct	367 ms	780388 KB	Output is correct
3	Correct	361 ms	780256 KB	Output is correct
4	Correct	360 ms	780388 KB	Output is correct
5	Correct	359 ms	780388 KB	Output is correct
6	Correct	366 ms	780300 KB	Output is correct
7	Correct	364 ms	780300 KB	Output is correct
8	Correct	363 ms	780388 KB	Output is correct
9	Correct	363 ms	780260 KB	Output is correct
10	Correct	367 ms	780260 KB	Output is correct
11	Correct	360 ms	780388 KB	Output is correct
12	Correct	367 ms	780388 KB	Output is correct
13	Correct	360 ms	780388 KB	Output is correct
14	Correct	362 ms	780392 KB	Output is correct
15	Correct	362 ms	780520 KB	Output is correct
16	Correct	360 ms	780392 KB	Output is correct
17	Correct	357 ms	780388 KB	Output is correct
18	Correct	364 ms	780424 KB	Output is correct
19	Correct	366 ms	780388 KB	Output is correct
20	Correct	364 ms	780388 KB	Output is correct
21	Correct	360 ms	780392 KB	Output is correct
22	Correct	366 ms	780388 KB	Output is correct
23	Correct	360 ms	780260 KB	Output is correct
24	Correct	362 ms	780516 KB	Output is correct
25	Correct	367 ms	780260 KB	Output is correct
26	Correct	362 ms	780260 KB	Output is correct
27	Correct	361 ms	780388 KB	Output is correct
28	Correct	360 ms	780260 KB	Output is correct
29	Correct	362 ms	780260 KB	Output is correct
30	Correct	366 ms	780408 KB	Output is correct
31	Correct	365 ms	780388 KB	Output is correct
32	Correct	362 ms	780356 KB	Output is correct
33	Correct	365 ms	780356 KB	Output is correct
34	Correct	360 ms	780260 KB	Output is correct
35	Correct	369 ms	780284 KB	Output is correct
36	Correct	363 ms	780260 KB	Output is correct
37	Correct	362 ms	780260 KB	Output is correct
38	Correct	363 ms	780260 KB	Output is correct
39	Correct	365 ms	780388 KB	Output is correct
40	Correct	363 ms	780260 KB	Output is correct
41	Correct	370 ms	780388 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	370 ms	780328 KB	Output is correct
2	Correct	366 ms	780436 KB	Output is correct
3	Correct	374 ms	780288 KB	Output is correct
4	Correct	366 ms	780388 KB	Output is correct
5	Correct	382 ms	780376 KB	Output is correct
6	Correct	365 ms	780392 KB	Output is correct
7	Correct	367 ms	780260 KB	Output is correct
8	Correct	367 ms	780388 KB	Output is correct
9	Correct	367 ms	780388 KB	Output is correct
10	Correct	359 ms	780388 KB	Output is correct
11	Correct	365 ms	780284 KB	Output is correct
12	Correct	361 ms	780260 KB	Output is correct
13	Correct	379 ms	780388 KB	Output is correct
14	Correct	370 ms	780300 KB	Output is correct
15	Correct	362 ms	780324 KB	Output is correct
16	Correct	372 ms	780520 KB	Output is correct

Subtask #4
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	369 ms	780260 KB	Output is correct
2	Correct	367 ms	780388 KB	Output is correct
3	Correct	361 ms	780256 KB	Output is correct
4	Correct	360 ms	780388 KB	Output is correct
5	Correct	359 ms	780388 KB	Output is correct
6	Correct	366 ms	780300 KB	Output is correct
7	Correct	364 ms	780300 KB	Output is correct
8	Correct	363 ms	780388 KB	Output is correct
9	Correct	363 ms	780260 KB	Output is correct
10	Correct	367 ms	780260 KB	Output is correct
11	Correct	360 ms	780388 KB	Output is correct
12	Correct	367 ms	780388 KB	Output is correct
13	Correct	360 ms	780388 KB	Output is correct
14	Correct	362 ms	780392 KB	Output is correct
15	Correct	362 ms	780520 KB	Output is correct
16	Correct	360 ms	780392 KB	Output is correct
17	Correct	357 ms	780388 KB	Output is correct
18	Correct	364 ms	780424 KB	Output is correct
19	Correct	366 ms	780388 KB	Output is correct
20	Correct	364 ms	780388 KB	Output is correct
21	Correct	360 ms	780392 KB	Output is correct
22	Correct	366 ms	780388 KB	Output is correct
23	Correct	360 ms	780260 KB	Output is correct
24	Correct	362 ms	780516 KB	Output is correct
25	Correct	367 ms	780260 KB	Output is correct
26	Correct	362 ms	780260 KB	Output is correct
27	Correct	361 ms	780388 KB	Output is correct
28	Correct	360 ms	780260 KB	Output is correct
29	Correct	362 ms	780260 KB	Output is correct
30	Correct	366 ms	780408 KB	Output is correct
31	Correct	365 ms	780388 KB	Output is correct
32	Correct	362 ms	780356 KB	Output is correct
33	Correct	365 ms	780356 KB	Output is correct
34	Correct	360 ms	780260 KB	Output is correct
35	Correct	369 ms	780284 KB	Output is correct
36	Correct	363 ms	780260 KB	Output is correct
37	Correct	362 ms	780260 KB	Output is correct
38	Correct	363 ms	780260 KB	Output is correct
39	Correct	365 ms	780388 KB	Output is correct
40	Correct	363 ms	780260 KB	Output is correct
41	Correct	370 ms	780388 KB	Output is correct
42	Correct	370 ms	780328 KB	Output is correct
43	Correct	366 ms	780436 KB	Output is correct
44	Correct	374 ms	780288 KB	Output is correct
45	Correct	366 ms	780388 KB	Output is correct
46	Correct	382 ms	780376 KB	Output is correct
47	Correct	365 ms	780392 KB	Output is correct
48	Correct	367 ms	780260 KB	Output is correct
49	Correct	367 ms	780388 KB	Output is correct
50	Correct	367 ms	780388 KB	Output is correct
51	Correct	359 ms	780388 KB	Output is correct
52	Correct	365 ms	780284 KB	Output is correct
53	Correct	361 ms	780260 KB	Output is correct
54	Correct	379 ms	780388 KB	Output is correct
55	Correct	370 ms	780300 KB	Output is correct
56	Correct	362 ms	780324 KB	Output is correct
57	Correct	372 ms	780520 KB	Output is correct
58	Correct	465 ms	780260 KB	Output is correct
59	Correct	465 ms	780520 KB	Output is correct
60	Correct	466 ms	780264 KB	Output is correct
61	Correct	468 ms	780388 KB	Output is correct
62	Correct	375 ms	780264 KB	Output is correct
63	Correct	381 ms	780260 KB	Output is correct
64	Correct	425 ms	780388 KB	Output is correct
65	Correct	441 ms	780344 KB	Output is correct
66	Correct	468 ms	780388 KB	Output is correct
67	Correct	457 ms	780388 KB	Output is correct
68	Correct	467 ms	780388 KB	Output is correct
69	Correct	461 ms	780296 KB	Output is correct
70	Correct	478 ms	780384 KB	Output is correct
71	Correct	467 ms	780392 KB	Output is correct
72	Correct	391 ms	780260 KB	Output is correct
73	Correct	370 ms	780260 KB	Output is correct

Submission #319656

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 15.0 / 15.0

Subtask #4 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
15.0 / 15.0

Subtask #4
25.0 / 25.0