#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
const int N = 401;
int n, dp[N][N][N][3], sum[N][3], pos[N][3];
string s;
int get_sum(int idx, int l, int r){
if(r < l || l == -1 || r == -1) return 0;
return sum[r][idx] - (l == 0 ? 0 : sum[l - 1][idx]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(pos, -1, sizeof pos);
cin >> n >> s;
for(int i = 0 ; i < n ; i++){
if(s[i] == 'R') s[i] = 0;
else if(s[i] == 'G') s[i] = 1;
else s[i] = 2;
for(int j = 0 ; j < 3 ; j++){
if(i > 0) sum[i][j] = sum[i - 1][j];
sum[i][j] += s[i] == j;
}
}
int pt0 = 0, pt1 = 0, pt2 = 0;
vector <int> cnt(3);
for(int i = 0 ; i < n ; i++){
if(s[i] == 0) pos[pt0++][0] = i;
else if(s[i] == 1) pos[pt1++][1] = i;
else pos[pt2++][2] = i;
cnt[s[i]]++;
}
for(int a = 0 ; a <= n ; a++){
for(int b = 0 ; b <= n ; b++){
for(int c = 0 ; c <= n ; c++){
for(int las = 0 ; las < 3 ; las++){
dp[a][b][c][las] = 1e9;
}
}
}
}
for(int las = 0 ; las < 3 ; las++){
dp[0][0][0][las] = 0;
}
for(int a = 0 ; a <= cnt[0] ; a++){
for(int b = 0 ; b <= cnt[1] ; b++){
for(int c = 0 ; c <= cnt[2] ; c++){
for(int las = 0 ; las < 3 ; las++){
if((las != 0 || a + b + c == 0) && pos[a][0] != -1){
dp[a + 1][b][c][0] = min(dp[a + 1][b][c][0], dp[a][b][c][las] + get_sum(1, pos[b][1], pos[a][0]) + get_sum(2, pos[c][2], pos[a][0]));
}
if((las != 1 || a + b + c == 0) && pos[b][1] != -1){
dp[a][b + 1][c][1] = min(dp[a][b + 1][c][1], dp[a][b][c][las] + get_sum(0, pos[a][0], pos[b][1]) + get_sum(2, pos[c][2], pos[b][1]));
}
if((las != 2 || a + b + c == 0) && pos[c][2] != -1){
dp[a][b][c + 1][2] = min(dp[a][b][c + 1][2], dp[a][b][c][las] + get_sum(0, pos[a][0], pos[c][2]) + get_sum(1, pos[b][1], pos[c][2]));
}
}
}
}
}
int ans = min(min(dp[cnt[0]][cnt[1]][cnt[2]][0], dp[cnt[0]][cnt[1]][cnt[2]][1]), dp[cnt[0]][cnt[1]][cnt[2]][2]);
if(ans == 1e9) ans = -1;
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
2 ms |
1536 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1536 KB |
Output is correct |
8 |
Correct |
1 ms |
1536 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1536 KB |
Output is correct |
11 |
Correct |
1 ms |
1408 KB |
Output is correct |
12 |
Correct |
1 ms |
1408 KB |
Output is correct |
13 |
Correct |
1 ms |
1408 KB |
Output is correct |
14 |
Correct |
1 ms |
1280 KB |
Output is correct |
15 |
Correct |
1 ms |
1408 KB |
Output is correct |
16 |
Correct |
1 ms |
1536 KB |
Output is correct |
17 |
Correct |
1 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
2 ms |
1536 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1536 KB |
Output is correct |
8 |
Correct |
1 ms |
1536 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1536 KB |
Output is correct |
11 |
Correct |
1 ms |
1408 KB |
Output is correct |
12 |
Correct |
1 ms |
1408 KB |
Output is correct |
13 |
Correct |
1 ms |
1408 KB |
Output is correct |
14 |
Correct |
1 ms |
1280 KB |
Output is correct |
15 |
Correct |
1 ms |
1408 KB |
Output is correct |
16 |
Correct |
1 ms |
1536 KB |
Output is correct |
17 |
Correct |
1 ms |
1280 KB |
Output is correct |
18 |
Correct |
11 ms |
18048 KB |
Output is correct |
19 |
Correct |
11 ms |
18048 KB |
Output is correct |
20 |
Correct |
11 ms |
18048 KB |
Output is correct |
21 |
Correct |
12 ms |
18048 KB |
Output is correct |
22 |
Correct |
11 ms |
18048 KB |
Output is correct |
23 |
Correct |
11 ms |
18048 KB |
Output is correct |
24 |
Correct |
9 ms |
18048 KB |
Output is correct |
25 |
Correct |
9 ms |
18048 KB |
Output is correct |
26 |
Correct |
10 ms |
18048 KB |
Output is correct |
27 |
Correct |
9 ms |
18048 KB |
Output is correct |
28 |
Correct |
10 ms |
18048 KB |
Output is correct |
29 |
Correct |
9 ms |
18048 KB |
Output is correct |
30 |
Correct |
9 ms |
18048 KB |
Output is correct |
31 |
Correct |
11 ms |
18048 KB |
Output is correct |
32 |
Correct |
9 ms |
18048 KB |
Output is correct |
33 |
Correct |
10 ms |
17536 KB |
Output is correct |
34 |
Correct |
9 ms |
17536 KB |
Output is correct |
35 |
Correct |
10 ms |
16896 KB |
Output is correct |
36 |
Correct |
12 ms |
17536 KB |
Output is correct |
37 |
Correct |
8 ms |
16256 KB |
Output is correct |
38 |
Correct |
13 ms |
18048 KB |
Output is correct |
39 |
Correct |
9 ms |
18048 KB |
Output is correct |
40 |
Correct |
10 ms |
17536 KB |
Output is correct |
41 |
Correct |
11 ms |
18048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
403 ms |
757500 KB |
Output is correct |
3 |
Correct |
397 ms |
755340 KB |
Output is correct |
4 |
Correct |
396 ms |
757496 KB |
Output is correct |
5 |
Correct |
396 ms |
757496 KB |
Output is correct |
6 |
Correct |
404 ms |
757432 KB |
Output is correct |
7 |
Correct |
404 ms |
755452 KB |
Output is correct |
8 |
Correct |
397 ms |
755320 KB |
Output is correct |
9 |
Correct |
436 ms |
751480 KB |
Output is correct |
10 |
Correct |
442 ms |
757500 KB |
Output is correct |
11 |
Correct |
396 ms |
757496 KB |
Output is correct |
12 |
Correct |
102 ms |
202744 KB |
Output is correct |
13 |
Correct |
185 ms |
357416 KB |
Output is correct |
14 |
Correct |
285 ms |
517500 KB |
Output is correct |
15 |
Correct |
412 ms |
757496 KB |
Output is correct |
16 |
Correct |
437 ms |
757496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
2 ms |
1536 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1536 KB |
Output is correct |
8 |
Correct |
1 ms |
1536 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1536 KB |
Output is correct |
11 |
Correct |
1 ms |
1408 KB |
Output is correct |
12 |
Correct |
1 ms |
1408 KB |
Output is correct |
13 |
Correct |
1 ms |
1408 KB |
Output is correct |
14 |
Correct |
1 ms |
1280 KB |
Output is correct |
15 |
Correct |
1 ms |
1408 KB |
Output is correct |
16 |
Correct |
1 ms |
1536 KB |
Output is correct |
17 |
Correct |
1 ms |
1280 KB |
Output is correct |
18 |
Correct |
11 ms |
18048 KB |
Output is correct |
19 |
Correct |
11 ms |
18048 KB |
Output is correct |
20 |
Correct |
11 ms |
18048 KB |
Output is correct |
21 |
Correct |
12 ms |
18048 KB |
Output is correct |
22 |
Correct |
11 ms |
18048 KB |
Output is correct |
23 |
Correct |
11 ms |
18048 KB |
Output is correct |
24 |
Correct |
9 ms |
18048 KB |
Output is correct |
25 |
Correct |
9 ms |
18048 KB |
Output is correct |
26 |
Correct |
10 ms |
18048 KB |
Output is correct |
27 |
Correct |
9 ms |
18048 KB |
Output is correct |
28 |
Correct |
10 ms |
18048 KB |
Output is correct |
29 |
Correct |
9 ms |
18048 KB |
Output is correct |
30 |
Correct |
9 ms |
18048 KB |
Output is correct |
31 |
Correct |
11 ms |
18048 KB |
Output is correct |
32 |
Correct |
9 ms |
18048 KB |
Output is correct |
33 |
Correct |
10 ms |
17536 KB |
Output is correct |
34 |
Correct |
9 ms |
17536 KB |
Output is correct |
35 |
Correct |
10 ms |
16896 KB |
Output is correct |
36 |
Correct |
12 ms |
17536 KB |
Output is correct |
37 |
Correct |
8 ms |
16256 KB |
Output is correct |
38 |
Correct |
13 ms |
18048 KB |
Output is correct |
39 |
Correct |
9 ms |
18048 KB |
Output is correct |
40 |
Correct |
10 ms |
17536 KB |
Output is correct |
41 |
Correct |
11 ms |
18048 KB |
Output is correct |
42 |
Correct |
1 ms |
384 KB |
Output is correct |
43 |
Correct |
403 ms |
757500 KB |
Output is correct |
44 |
Correct |
397 ms |
755340 KB |
Output is correct |
45 |
Correct |
396 ms |
757496 KB |
Output is correct |
46 |
Correct |
396 ms |
757496 KB |
Output is correct |
47 |
Correct |
404 ms |
757432 KB |
Output is correct |
48 |
Correct |
404 ms |
755452 KB |
Output is correct |
49 |
Correct |
397 ms |
755320 KB |
Output is correct |
50 |
Correct |
436 ms |
751480 KB |
Output is correct |
51 |
Correct |
442 ms |
757500 KB |
Output is correct |
52 |
Correct |
396 ms |
757496 KB |
Output is correct |
53 |
Correct |
102 ms |
202744 KB |
Output is correct |
54 |
Correct |
185 ms |
357416 KB |
Output is correct |
55 |
Correct |
285 ms |
517500 KB |
Output is correct |
56 |
Correct |
412 ms |
757496 KB |
Output is correct |
57 |
Correct |
437 ms |
757496 KB |
Output is correct |
58 |
Correct |
449 ms |
757420 KB |
Output is correct |
59 |
Correct |
462 ms |
757528 KB |
Output is correct |
60 |
Correct |
487 ms |
751480 KB |
Output is correct |
61 |
Correct |
478 ms |
755320 KB |
Output is correct |
62 |
Correct |
457 ms |
757496 KB |
Output is correct |
63 |
Correct |
434 ms |
757496 KB |
Output is correct |
64 |
Correct |
473 ms |
757496 KB |
Output is correct |
65 |
Correct |
426 ms |
755284 KB |
Output is correct |
66 |
Correct |
440 ms |
748024 KB |
Output is correct |
67 |
Correct |
489 ms |
757496 KB |
Output is correct |
68 |
Correct |
476 ms |
755272 KB |
Output is correct |
69 |
Correct |
480 ms |
757556 KB |
Output is correct |
70 |
Correct |
469 ms |
757416 KB |
Output is correct |
71 |
Correct |
482 ms |
755320 KB |
Output is correct |
72 |
Correct |
427 ms |
755324 KB |
Output is correct |
73 |
Correct |
406 ms |
757496 KB |
Output is correct |