#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;
string w = "GRY";
string s;
int dp[N][N][N][3], n, pre[N][3];
vector <int> pos[3];
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;
memset (dp, 63, sizeof dp);
dp[0][0][0][1] = dp[0][0][0][2] = dp[0][0][0][0] = 0;
forr (i, 1, n){
forr (j, 0, 2){
pre[i][j] = pre[i - 1][j];
if (s[i - 1] == w[j]){
pos[j].pb(i);
pre[i][j]++;
}
}
}
forr (i, 0, pos[0].size()){
forr (j, 0, pos[1].size()){
forr (k, 0, pos[2].size()){
forr (t, 0, 2)
if(dp[i][j][k][t] < mod){
if (t != 0 && i < pos[0].size()){
int tmp1 = max(pre[pos[0][i]][1] - j, 0);
int tmp2 = max(pre[pos[0][i]][2] - k, 0);
minz(dp[i + 1][j][k][0], dp[i][j][k][t] + tmp1 + tmp2);
}
if (t != 1 && j < pos[1].size()){
int tmp1 = max(pre[0][pos[1][j]] - i, 0);
int tmp2 = max(pre[2][pos[1][j]] - k, 0);
minz(dp[i][j + 1][k][1], dp[i][j][k][t] + tmp1 + tmp2);
}
if(t != 2 && k < pos[2].size()){
int tmp1 = max(pre[0][pos[2][k]] - i, 0);
int tmp2 = max(pre[1][pos[2][k]] - j, 0);
minz(dp[i][j][k + 1][2], dp[i][j][k][t] + tmp1 + tmp2);
}
}
}
}
}
int res = mod;
forr (t, 0, 2){
minz(res, dp[pos[0].size()][pos[1].size()][pos[2].size()][t]);
}
cout << (res == mod ? -1 : res * 2) << "\n";
return 0;
}
/*
*/
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:73:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (t != 0 && i < pos[0].size()){
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:79:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if (t != 1 && j < pos[1].size()){
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:85:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | if(t != 2 && k < pos[2].size()){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
780624 KB |
Output is correct |
| 2 |
Correct |
96 ms |
780360 KB |
Output is correct |
| 3 |
Incorrect |
107 ms |
780360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
780624 KB |
Output is correct |
| 2 |
Correct |
96 ms |
780360 KB |
Output is correct |
| 3 |
Incorrect |
107 ms |
780360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
780376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
780624 KB |
Output is correct |
| 2 |
Correct |
96 ms |
780360 KB |
Output is correct |
| 3 |
Incorrect |
107 ms |
780360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
