#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
int n;
int a[3][maxn], b[maxn][3], cnt[3];
int f[2][maxn][maxn][3];
char s[maxn];
inline int calc(int i, int j, int k, int l){
return max(j - b[i][0], 0) + max(k - b[i][1], 0) + max(l - b[i][2], 0);
}
int main(){
//freopen("b.in", "r", stdin);
//freopen("b.out", "w", stdout);
scanf("%d", &n);
scanf("%s", s);
for(int i = 0; i < n; ++i){
for(int j = 0; j < 3; ++j)
b[i][j] = cnt[j];
s[i] = (s[i] == 'R' ? 2 : (s[i] == 'G'));
a[s[i]][cnt[s[i]]++] = i;
}
int p = 0, q = 1;
memset(f[p], 0x3f, sizeof(f[p]));
if(cnt[0])
f[p][1][0][0] = 0;
if(cnt[1])
f[p][0][1][1] = 0;
if(cnt[2])
f[p][0][0][2] = 0;
for(int i = 1; i <= n - 1; ++i){
memset(f[q], 0x3f, sizeof(f[q]));
for(int j = 0; j <= i; ++j)
for(int k = 0; k <= i - j; ++k){
int l = i - j - k;
for(int s = 0; s < 3; ++s)
if(f[p][j][k][s] != 0x3f3f3f3f){
if(s != 0 && j + 1 <= cnt[0])
f[q][j + 1][k][0] = min(f[q][j + 1][k][0], f[p][j][k][s] + calc(a[0][j], j, k, l));
if(s != 1 && k + 1 <= cnt[1])
f[q][j][k + 1][1] = min(f[q][j][k + 1][1], f[p][j][k][s] + calc(a[1][k], j, k, l));
if(s != 2 && l + 1 <= cnt[2])
f[q][j][k][2] = min(f[q][j][k][2] , f[p][j][k][s] + calc(a[2][l], j, k, l));
}
}
swap(p, q);
}
int ans = 0x3f3f3f3f;
for(int i = 0; i < 3; ++i)
ans = min(ans, f[p][cnt[0]][cnt[1]][i]);
printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}
Compilation message
joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:28:10: warning: array subscript has type 'char' [-Wchar-subscripts]
28 | a[s[i]][cnt[s[i]]++] = i;
| ~~~^
joi2019_ho_t2.cpp:28:20: warning: array subscript has type 'char' [-Wchar-subscripts]
28 | a[s[i]][cnt[s[i]]++] = i;
| ~~~^
joi2019_ho_t2.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
joi2019_ho_t2.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | scanf("%s", s);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2124 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2124 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2124 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
