#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
template<class X, class Y>
bool minz(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} return false;
}
template<class X, class Y>
bool maxz(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} return false;
}
const int N = 4e2 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
ll n, dp[N][N][N][3], c[3];
string s;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef kaguya
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
cin >> n >> s;
s = '#' + s;
memset (dp, 63, sizeof dp);
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
forr (i, 1, n){
if (s[i] == 'R'){
c[0]++;
} else if (s[i] == 'G'){
c[1]++;
} else {
c[2]++;
}
forf (j, 0, i){
forr (k, 0, i - j){
forr (t, 0, 2){
forr (w, 0, 2){
if (w == t) continue;
int nj = j, nk = k;
if (w == 0){
nj++;
} else if (w == 1){
nk++;
}
minz(dp[i][nj][nk][w], dp[i - 1][j][k][t]);
}
}
}
}
forr (j, 0, i){
forr (k, 0, i - j){
forr (t, 0, 2){
dp[i][j][k][t] += abs(c[0] - j) + abs(c[1] - k) + abs(c[2] - (i - j - k));
}
}
}
// forr (j, 0, i){
// forr (k, 0, i - j){
// cout << dp[i][j][k][0] << " " << dp[i][j][k][1] << " " << dp[i][j][k][2] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
}
ll res = oo;
forr (i, 0, 2)
minz (res, dp[n][c[0]][c[1]][i]);
cout << (res >= oo ? -1 : res / 2) << "\n";
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
143 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
