#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
ll dp[401][401][401][3];
vector<int> a , b , c;
ll rec(int i , int j , int k , int col , int s1 , int s2 , int s3){
if(i == s1 && j == s2 && k == s3)return 0;
if(dp[i][j][k][col]!=-1)return dp[i][j][k][col];
if(col == 0){
if(i == s1)return 1e9;
int p = upper_bound(all(b) , a[i]) - b.begin();
p = max(0 , j - p);
int p1 = upper_bound(all(c) , a[i]) - c.begin();
p1 = max(0 , k - p1);
int pos = a[i] + p + p1;
return dp[i][j][k][col] = abs(pos - (i + j + k)) + min(rec(i + 1 , j , k , 1 , s1 , s2 , s3) , rec(i + 1 , j , k , 2 , s1 , s2 , s3));
}
if(col == 1){
if(j == s2)return 1e9;
int p = upper_bound(all(a) , b[j]) - a.begin();
p = max(0 , i - p);
int p1 = upper_bound(all(c) , b[j]) - c.begin();
p1 = max(0 , k - p1);
int pos = b[j] + p + p1;
return dp[i][j][k][col] = abs(pos - (i + j + k)) + min(rec(i , j + 1 , k , 0 , s1, s2 , s3) , rec(i , j + 1 , k , 2 , s1 , s2 , s3));
}
if(k == s3)return 1e9;
int p = upper_bound(all(a) , c[k]) - a.begin();
p = max(0 , i - p);
int p1 = upper_bound(all(b) , c[k]) - b.begin();
p1 = max(0 , j - p1);
int pos = c[k] + p + p1;
return dp[i][j][k][col] = abs(pos - (i + j + k)) + min(rec(i , j , k + 1 , 0 ,s1 , s2 ,s3) , rec(i , j , k + 1 , 1 , s1 , s2 , s3));
}
void solve(){
int n;
cin >> n;
string s;
cin >> s;
for(int i = 0; i < n; i++){
if(s[i]=='R')a.pb(i);
else if(s[i] == 'G')b.pb(i);
else c.pb(i);
}
memset(dp,-1,sizeof dp);
ll ans = min({rec(0,0,0,0,a.size(),b.size(),c.size()),rec(0,0,0,1,a.size(),b.size(),c.size()),rec(0,0,0,2,a.size(),b.size(),c.size())});
if(ans >= 1e9)ans = -1;
cout << ans << '\n';
/*ll dp[a.size() + 1][b.size() + 1][c.size() + 1][3];
ll ans = 1e9;
for(int i = 0; i <= (int)a.size() + 1; i++){
for(int j = 0; j <= (int)b.size() + 1; j++){
for(int k = 0; k <= (int)c.size() + 1; k++){
dp[i][j][k][2] = dp[i][j][k][1] = dp[i][j][k][0] = 1e9;
if(k < (int)c.size()){
int p = upper_bound(all(a) , c[k]) - a.begin();
int p1 = upper_bound(all(b) , c[k]) - b.begin();
int pos = c[k] + p + p1;
dp[i][j][k][2] = min(dp[i][j][k][2] , abs(pos - (i + j + k)) + min(dp[i][j][k-1][0] , dp[i][j][k-1][1]));
}
if(j < (int)b.size()){
int p = upper_bound(all(a) , b[j]) - a.begin();
int p1 = upper_bound(all(c) , b[j]) - c.begin();
int pos = b[j] + p + p1;
dp[i][j][k][1] = min(dp[i][j][k][1] , abs(pos - (i + j + k)) + min(dp[i][j-1][k][0] , dp[i][j-1][k][2]));
}
if(i < (int)a.size()){
int p = upper_bound(all(b) , a[i]) - b.begin();
int p1 = upper_bound(all(c) , a[i]) - c.begin();
int pos = a[i] + p + p1;
dp[i][j][k][0] = min(dp[i][j][k][0] , abs(pos - (i + j + k)) + min(dp[i-1][j][k][1] , dp[i-1][j][k][2]));
}
if(a.size() + b.size() + c.size() == i + j + k + 1){
ans = min({ans , dp[i][j][k][0] , dp[i][j][k][1] , dp[i][j][k][2]});
}
}
}
}
cout << ans << '\n';*/
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin >> t;while(t--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
343 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
