#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int N;
char str[440];
vector<int> R, G, Y;
int D[4][404][404][404];
int f(int l, int r, int g, int y){
if (r+g+y >= N) return 0;
if ((int)R.size()-r > (int)G.size()-g+(int)Y.size()-y+1) return INF;
if ((int)G.size()-g > (int)R.size()-r+(int)Y.size()-y+1) return INF;
if ((int)Y.size()-y > (int)R.size()-r+(int)G.size()-g+1) return INF;
if (D[l][r][g][y] != INF) return D[l][r][g][y];
if (l != 0 && r < (int)R.size()){
int ret = f(0, r+1, g, y);
ret += max(0, g - (int)(lower_bound(G.begin(), G.end(), R[r]) - G.begin()));
ret += max(0, y - (int)(lower_bound(Y.begin(), Y.end(), R[r]) - Y.begin()));
D[l][r][g][y] = min(D[l][r][g][y], ret);
}
if (l != 1 && g < (int)G.size()){
int ret = f(1, r, g+1, y);
ret += max(0, r - (int)(lower_bound(R.begin(), R.end(), G[g]) - R.begin()));
ret += max(0, y - (int)(lower_bound(Y.begin(), Y.end(), G[g]) - Y.begin()));
D[l][r][g][y] = min(D[l][r][g][y], ret);
}
if (l != 2 && y < (int)Y.size()){
int ret = f(2, r, g, y+1);
ret += max(0, r - (int)(lower_bound(R.begin(), R.end(), Y[y]) - R.begin()));
ret += max(0, g - (int)(lower_bound(G.begin(), G.end(), Y[y]) - G.begin()));
D[l][r][g][y] = min(D[l][r][g][y], ret);
}
return D[l][r][g][y];
}
int main(){
scanf("%d", &N);
scanf("%s", str+1);
for (int i=1; i<=N; i++){
if (str[i] == 'R') R.push_back(i);
else if (str[i] == 'G') G.push_back(i);
else Y.push_back(i);
}
for (int i=0; i<4; i++){
for (int j=0; j<=(int)R.size(); j++){
for (int k=0; k<=(int)G.size(); k++){
for (int l=0; l<=(int)Y.size(); l++){
D[i][j][k][l] = INF;
}
}
}
}
int ans = f(3, 0, 0, 0);
if (ans == INF) puts("-1");
else printf("%d\n", ans);
return 0;
}
// RRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGYYYYYYYYYYYYYYYYYYYY
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str+1);
~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
768 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
3 ms |
896 KB |
Output is correct |
10 |
Correct |
3 ms |
896 KB |
Output is correct |
11 |
Correct |
2 ms |
768 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
768 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
640 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
768 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
3 ms |
896 KB |
Output is correct |
10 |
Correct |
3 ms |
896 KB |
Output is correct |
11 |
Correct |
2 ms |
768 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
768 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
640 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
3584 KB |
Output is correct |
19 |
Correct |
4 ms |
2944 KB |
Output is correct |
20 |
Correct |
5 ms |
3456 KB |
Output is correct |
21 |
Correct |
5 ms |
3712 KB |
Output is correct |
22 |
Correct |
3 ms |
2560 KB |
Output is correct |
23 |
Correct |
5 ms |
3328 KB |
Output is correct |
24 |
Correct |
3 ms |
2304 KB |
Output is correct |
25 |
Correct |
6 ms |
6400 KB |
Output is correct |
26 |
Correct |
6 ms |
6656 KB |
Output is correct |
27 |
Correct |
5 ms |
4864 KB |
Output is correct |
28 |
Correct |
5 ms |
3584 KB |
Output is correct |
29 |
Correct |
5 ms |
3456 KB |
Output is correct |
30 |
Correct |
5 ms |
3456 KB |
Output is correct |
31 |
Correct |
4 ms |
2944 KB |
Output is correct |
32 |
Correct |
5 ms |
3584 KB |
Output is correct |
33 |
Correct |
6 ms |
6144 KB |
Output is correct |
34 |
Correct |
6 ms |
5632 KB |
Output is correct |
35 |
Correct |
5 ms |
4144 KB |
Output is correct |
36 |
Correct |
4 ms |
2944 KB |
Output is correct |
37 |
Correct |
4 ms |
2560 KB |
Output is correct |
38 |
Correct |
4 ms |
3200 KB |
Output is correct |
39 |
Correct |
5 ms |
3584 KB |
Output is correct |
40 |
Correct |
2 ms |
512 KB |
Output is correct |
41 |
Correct |
4 ms |
3328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
194 ms |
258400 KB |
Output is correct |
3 |
Correct |
165 ms |
257144 KB |
Output is correct |
4 |
Correct |
174 ms |
258304 KB |
Output is correct |
5 |
Correct |
177 ms |
258312 KB |
Output is correct |
6 |
Correct |
178 ms |
258352 KB |
Output is correct |
7 |
Correct |
186 ms |
257056 KB |
Output is correct |
8 |
Correct |
176 ms |
256992 KB |
Output is correct |
9 |
Correct |
173 ms |
255736 KB |
Output is correct |
10 |
Correct |
172 ms |
258360 KB |
Output is correct |
11 |
Correct |
176 ms |
258328 KB |
Output is correct |
12 |
Correct |
50 ms |
70128 KB |
Output is correct |
13 |
Correct |
83 ms |
122608 KB |
Output is correct |
14 |
Correct |
118 ms |
176692 KB |
Output is correct |
15 |
Correct |
172 ms |
258232 KB |
Output is correct |
16 |
Correct |
170 ms |
258208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
768 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
3 ms |
896 KB |
Output is correct |
10 |
Correct |
3 ms |
896 KB |
Output is correct |
11 |
Correct |
2 ms |
768 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
768 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
640 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
3584 KB |
Output is correct |
19 |
Correct |
4 ms |
2944 KB |
Output is correct |
20 |
Correct |
5 ms |
3456 KB |
Output is correct |
21 |
Correct |
5 ms |
3712 KB |
Output is correct |
22 |
Correct |
3 ms |
2560 KB |
Output is correct |
23 |
Correct |
5 ms |
3328 KB |
Output is correct |
24 |
Correct |
3 ms |
2304 KB |
Output is correct |
25 |
Correct |
6 ms |
6400 KB |
Output is correct |
26 |
Correct |
6 ms |
6656 KB |
Output is correct |
27 |
Correct |
5 ms |
4864 KB |
Output is correct |
28 |
Correct |
5 ms |
3584 KB |
Output is correct |
29 |
Correct |
5 ms |
3456 KB |
Output is correct |
30 |
Correct |
5 ms |
3456 KB |
Output is correct |
31 |
Correct |
4 ms |
2944 KB |
Output is correct |
32 |
Correct |
5 ms |
3584 KB |
Output is correct |
33 |
Correct |
6 ms |
6144 KB |
Output is correct |
34 |
Correct |
6 ms |
5632 KB |
Output is correct |
35 |
Correct |
5 ms |
4144 KB |
Output is correct |
36 |
Correct |
4 ms |
2944 KB |
Output is correct |
37 |
Correct |
4 ms |
2560 KB |
Output is correct |
38 |
Correct |
4 ms |
3200 KB |
Output is correct |
39 |
Correct |
5 ms |
3584 KB |
Output is correct |
40 |
Correct |
2 ms |
512 KB |
Output is correct |
41 |
Correct |
4 ms |
3328 KB |
Output is correct |
42 |
Correct |
2 ms |
384 KB |
Output is correct |
43 |
Correct |
194 ms |
258400 KB |
Output is correct |
44 |
Correct |
165 ms |
257144 KB |
Output is correct |
45 |
Correct |
174 ms |
258304 KB |
Output is correct |
46 |
Correct |
177 ms |
258312 KB |
Output is correct |
47 |
Correct |
178 ms |
258352 KB |
Output is correct |
48 |
Correct |
186 ms |
257056 KB |
Output is correct |
49 |
Correct |
176 ms |
256992 KB |
Output is correct |
50 |
Correct |
173 ms |
255736 KB |
Output is correct |
51 |
Correct |
172 ms |
258360 KB |
Output is correct |
52 |
Correct |
176 ms |
258328 KB |
Output is correct |
53 |
Correct |
50 ms |
70128 KB |
Output is correct |
54 |
Correct |
83 ms |
122608 KB |
Output is correct |
55 |
Correct |
118 ms |
176692 KB |
Output is correct |
56 |
Correct |
172 ms |
258232 KB |
Output is correct |
57 |
Correct |
170 ms |
258208 KB |
Output is correct |
58 |
Correct |
279 ms |
102724 KB |
Output is correct |
59 |
Correct |
288 ms |
130044 KB |
Output is correct |
60 |
Correct |
275 ms |
118352 KB |
Output is correct |
61 |
Correct |
275 ms |
114308 KB |
Output is correct |
62 |
Correct |
168 ms |
251868 KB |
Output is correct |
63 |
Correct |
167 ms |
248300 KB |
Output is correct |
64 |
Correct |
168 ms |
216896 KB |
Output is correct |
65 |
Correct |
187 ms |
188656 KB |
Output is correct |
66 |
Correct |
216 ms |
115996 KB |
Output is correct |
67 |
Correct |
211 ms |
111448 KB |
Output is correct |
68 |
Correct |
229 ms |
119460 KB |
Output is correct |
69 |
Correct |
232 ms |
115156 KB |
Output is correct |
70 |
Correct |
237 ms |
124572 KB |
Output is correct |
71 |
Correct |
235 ms |
113300 KB |
Output is correct |
72 |
Correct |
42 ms |
58488 KB |
Output is correct |
73 |
Correct |
4 ms |
3840 KB |
Output is correct |