#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
//typedef pair<pii,pii>pi2;
typedef array<int,6>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
string s;
vector<int>v[3];
int arr[401];
int memo2[3][401];
int dp[2][401][401][3];
int f(int color, int pos){
if(memo2[color][pos]!=-1) return memo2[color][pos];
int hold=lower_bound(v[color].begin(),v[color].end(),pos)-v[color].begin();
return memo2[color][pos]=hold;
}
int add(int a, int b){
return max(0LL,a+b);
}
void solve(){
cin >> n >> s;
for(int x=0;x<n;x++){
if(s[x]=='R'){
arr[x]=0;
}
else if(s[x]=='G'){
arr[x]=1;
}
else arr[x]=2;
v[arr[x]].push_back(x);
}
memset(memo2,-1,sizeof(memo2));
//iterative
for(int x=0;x<401;x++){
for(int y=0;y<401;y++){
for(int i=0;i<3;i++){
dp[0][x][y][i]=1e15;
dp[1][x][y][i]=1e15;
}
}
}
dp[0][0][0][0]=0;
for(int r=0;r<(int)v[0].size();r++){
for(int g=0;g<(int)v[1].size();g++){
for(int b=0;b<(int)v[2].size();b++){
for(int last=0;last<3;last++){
int index=r+g+b;
if(index==0){
dp[1][g][b][0]=min(dp[1][g][b][0],dp[0][g][b][last]+v[0][r]);
dp[0][g+1][b][1]=min(dp[0][g+1][b][1],dp[0][g][b][last]+v[1][g]);
dp[0][g][b+1][2]=min(dp[0][g][b+1][2],dp[0][g][b][last]+v[2][b]);
}
else{
if(last!=0){
int hold=f(1,v[0][r]);
int hold2=f(2,v[0][r]);
int cost=add(hold,-g)+add(hold2,-b);
dp[1][g][b][0]=min(dp[1][g][b][0],dp[0][g][b][last]+cost);
}
if(last!=1){
int hold=f(0,v[1][g]);
int hold2=f(2,v[1][g]);
int cost=add(hold,-r)+add(hold2,-b);
dp[0][g+1][b][1]=min(dp[0][g+1][b][1],dp[0][g][b][last]+cost);
}
if(last!=2){
int hold=f(0,v[2][b]);
int hold2=f(1,v[2][b]);
int cost=add(hold,-r)+add(hold2,-g);
dp[0][g][b+1][2]=min(dp[0][g][b+1][2],dp[0][g][b][last]+cost);
}
}
}
}
}
for(int g=0;g<(int)v[1].size();g++){
for(int b=0;b<(int)v[2].size();b++){
for(int last=0;last<3;last++){
dp[0][g][b][last]=dp[1][g][b][last];
dp[1][g][b][last]=1e15;
}
}
}
}
int ans=min({dp[0][v[1].size()-1][v[2].size()-1][0],dp[0][v[1].size()-1][v[2].size()-1][1],dp[0][v[1].size()-1][v[2].size()-1][2]});
if(ans>=1e12){
cout << -1;
}
else cout << ans;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
