#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e9 + 7;
inline int eval(int x , int y){
return max(0ll , x-y);
}
inline void ckmin(int &x , int y){
x = min(x,y);
}
void solve(){
int n;
cin >> n;
string str;
cin >> str;
vector < int > ind[3];
for(int i = 0;i<n;i++){
if(str[i] == 'R')ind[0].push_back(i);
else if(str[i] == 'G')ind[1].push_back(i);
else ind[2].push_back(i);
}
int dp[ind[0].size()+2][ind[1].size()+2][ind[2].size()+2][3];
for(int i = 0;i<=ind[0].size();i++){
for(int j = 0;j<=ind[1].size();j++){
for(int k = 0;k<=ind[2].size();k++){
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;
}
}
}
dp[0][0][0][0] = 0;
for(int cnt0 = 0;cnt0 <= (int)ind[0].size();cnt0++){
for(int cnt1 = 0;cnt1 <= (int)ind[1].size();cnt1++){
for(int cnt2 = 0;cnt2 <= (int)ind[2].size();cnt2++){
if(cnt0 != (int)ind[0].size()){
if(cnt0 == 0 and cnt1 == 0 and cnt2 == 0){
ckmin(dp[cnt0+1][cnt1][cnt2][0] , dp[cnt0][cnt1][cnt2][0] + eval(ind[0][cnt0] , cnt0+cnt1+cnt2));
}
ckmin(dp[cnt0+1][cnt1][cnt2][0] , dp[cnt0][cnt1][cnt2][1] + eval(ind[0][cnt0] , cnt0+cnt1+cnt2));
ckmin(dp[cnt0+1][cnt1][cnt2][0] , dp[cnt0][cnt1][cnt2][2] + eval(ind[0][cnt0] , cnt0+cnt1+cnt2));
}
if(cnt1 != (int)ind[1].size()){
ckmin(dp[cnt0][cnt1+1][cnt2][1] , dp[cnt0][cnt1][cnt2][0] + eval(ind[1][cnt1] , cnt0+cnt1+cnt2));
if(cnt0 == 0 and cnt1 == 0 and cnt2 == 0){
ckmin(dp[cnt0][cnt1+1][cnt2][1] , dp[cnt0][cnt1][cnt2][1] + eval(ind[1][cnt1] , cnt0+cnt1+cnt2));
}
ckmin(dp[cnt0][cnt1+1][cnt2][1] , dp[cnt0][cnt1][cnt2][2] + eval(ind[1][cnt1] , cnt0+cnt1+cnt2));
}
if(cnt2 != (int)ind[2].size()){
ckmin(dp[cnt0][cnt1][cnt2+1][2] , dp[cnt0][cnt1][cnt2][0] + eval(ind[2][cnt2] , cnt0+cnt1+cnt2));
ckmin(dp[cnt0][cnt1][cnt2+1][2] , dp[cnt0][cnt1][cnt2][1] + eval(ind[2][cnt2] , cnt0+cnt1+cnt2));
if(cnt0 == 0 and cnt1 == 0 and cnt2 == 0){
ckmin(dp[cnt0][cnt1][cnt2+1][2] , dp[cnt0][cnt1][cnt2][2] + eval(ind[2][cnt2] , cnt0+cnt1+cnt2));
}
}
}
}
}
int ans = inf;
for(int i = 0;i<3;i++){
ans = min(ans , dp[ind[0].size()][ind[1].size()][ind[2].size()][i]);
}
cout << (ans == inf ? -1 : ans) << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
Compilation message
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:23:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i = 0;i<=ind[0].size();i++){
| ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:24:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int j = 0;j<=ind[1].size();j++){
| ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:25:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int k = 0;k<=ind[2].size();k++){
| ~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
600 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
600 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2140 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2140 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
600 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
