#include<iostream>
#include<cassert>
#include<vector>
using namespace std;
int const N = 405;
int a[N], n;
int const R = 0, G = 1, Y = 2, inf = 1e9;
vector<int> point[3];
int dp[N][N][N][3], backp[3][N];
void solve(){
dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; dp[0][0][0][2] = 0;
for(int i = 0; i <= point[0].size(); i++){
for(int j = 0; j <= point[1].size(); j++){
for(int k = 0; k <= point[2].size(); k++){
if(!i && !j && !k)
continue;
for(int t = 0; t < 3; t++){
int backcnt = 0;
if((t == 0 && !i) || (t == 1 && !j) || (t == 2 && !k)){
dp[i][j][k][t] = inf;
continue;
}
if(t == 0){
if(j)
backcnt += max(j - backp[1][point[t][i - 1]], 0);
if(k)
backcnt += max(k - backp[2][point[t][i - 1]], 0);
dp[i][j][k][t] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + abs(point[0][i - 1] - (i + j + k - 1));
}else if(t == 1){
if(i)
backcnt += max(i - backp[0][point[t][j - 1]], 0);
if(k)
backcnt += max(k - backp[2][point[t][j - 1]], 0);
dp[i][j][k][t] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + abs(point[1][j - 1] - (i + j + k - 1));
}else if(t == 2){
if(i)
backcnt += max(i - backp[0][point[t][k - 1]], 0);
if(j)
backcnt += max(j - backp[1][point[t][k - 1]], 0);
dp[i][j][k][t] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + abs(point[2][k - 1] - (i + j + k - 1));
}
}
}
}
}
cout << min(dp[point[0].size()][point[1].size()][point[2].size()][0],min(dp[point[0].size()][point[1].size()][point[2].size()][1], dp[point[0].size()][point[1].size()][point[2].size()][2])) / 2 << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
char in;
if(n == 1){
cout << 0 << '\n';
return 0;
}
for(int i = 0; i < n; i++){
cin >> in;
if(in == 'R'){
a[i] = 0;
}else if(in == 'G')
a[i] = 1;
else{
a[i] = 2;
}
point[a[i]].push_back(i);
}
for(int i = 0; i < 3; i++){
if(point[i].size() > (n + 1) / 2){
cout << -1 << '\n';
return 0;
}
backp[i][n] = point[i].size();
int p = point[i].size() - 1;
for(int j = n - 1; j >= 0; j--){
if(p >= 0 && point[i][p] == j){
backp[i][j] = p;
p--;
}else{
backp[i][j] = backp[i][j + 1];
}
}
}
solve();
}
Compilation message
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i = 0; i <= point[0].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:13:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int j = 0; j <= point[1].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:14:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int k = 0; k <= point[2].size(); k++){
| ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:69:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if(point[i].size() > (n + 1) / 2){
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
588 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
588 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
320 KB |
Output is correct |
| 2 |
Correct |
58 ms |
162872 KB |
Output is correct |
| 3 |
Correct |
58 ms |
162116 KB |
Output is correct |
| 4 |
Correct |
58 ms |
162884 KB |
Output is correct |
| 5 |
Correct |
57 ms |
162940 KB |
Output is correct |
| 6 |
Correct |
56 ms |
162880 KB |
Output is correct |
| 7 |
Correct |
57 ms |
162116 KB |
Output is correct |
| 8 |
Correct |
62 ms |
162228 KB |
Output is correct |
| 9 |
Correct |
68 ms |
161308 KB |
Output is correct |
| 10 |
Correct |
60 ms |
162884 KB |
Output is correct |
| 11 |
Correct |
58 ms |
162952 KB |
Output is correct |
| 12 |
Correct |
18 ms |
43980 KB |
Output is correct |
| 13 |
Correct |
30 ms |
77060 KB |
Output is correct |
| 14 |
Correct |
49 ms |
111312 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
588 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
