#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 (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;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:38: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:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str+1);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
640 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 |
2 ms |
896 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
688 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
640 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 |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
640 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 |
2 ms |
896 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
688 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
640 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 |
Execution timed out |
1055 ms |
3584 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
167 ms |
258272 KB |
Output is correct |
3 |
Correct |
167 ms |
257060 KB |
Output is correct |
4 |
Correct |
170 ms |
258496 KB |
Output is correct |
5 |
Correct |
182 ms |
258296 KB |
Output is correct |
6 |
Correct |
166 ms |
258364 KB |
Output is correct |
7 |
Correct |
168 ms |
257016 KB |
Output is correct |
8 |
Correct |
166 ms |
256992 KB |
Output is correct |
9 |
Correct |
165 ms |
255836 KB |
Output is correct |
10 |
Correct |
170 ms |
258356 KB |
Output is correct |
11 |
Correct |
176 ms |
258296 KB |
Output is correct |
12 |
Correct |
52 ms |
70264 KB |
Output is correct |
13 |
Correct |
86 ms |
122616 KB |
Output is correct |
14 |
Correct |
122 ms |
176760 KB |
Output is correct |
15 |
Correct |
174 ms |
258300 KB |
Output is correct |
16 |
Correct |
174 ms |
258424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
640 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 |
2 ms |
896 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
688 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
640 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 |
Execution timed out |
1055 ms |
3584 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |