#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[100];
int f(int color, int pos){
int hold=lower_bound(v[color].begin(),v[color].end(),pos)-v[color].begin();
return hold;
}
int add(int a, int b){
return max(0LL,a+b);
}
int memo[401][401][401][3];
int dp(int r, int g, int b,int last){
int index=r+g+b;
if(index==n) return 0;
if(memo[r][g][b][last]!=-1) return memo[r][g][b][last];
int ans=1e15;
if(index==0){
//put red
if(r<(int)v[0].size())ans=min(ans,dp(r+1,g,b,0)+v[0][r]);
//put green
if(g<(int)v[1].size())ans=min(ans,dp(r,g+1,b,1)+v[1][g]);
//put blue
if(g<(int)v[2].size())ans=min(ans,dp(r,g,b+1,2)+v[2][b]);
}
else{
//put red
if(r<(int)v[0].size() && last!=0){
int hold=f(1,v[0][r]);
int hold2=f(2,v[0][r]);
int cost=add(hold,-g)+add(hold2,-b);
ans=min(ans,dp(r+1,g,b,0)+cost);
}
//put green
if(g<(int)v[1].size() && last!=1){
int hold=f(0,v[1][g]);
int hold2=f(2,v[1][g]);
int cost=add(hold,-r)+add(hold2,-b);
ans=min(ans,dp(r,g+1,b,1)+cost);
}
//put blue
if(b<(int)v[2].size() && last!=2){
int hold=f(0,v[2][b]);
int hold2=f(1,v[2][b]);
int cost=add(hold,-r)+add(hold2,-g);
ans=min(ans,dp(r,g,b+1,2)+cost);
}
}
return memo[r][g][b][last]=ans;
}
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(memo,-1,sizeof(memo));
int hold=dp(0,0,0,0);
if(hold>=1e10){
cout << -1;
}
else cout << hold;
}
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 |
Execution timed out |
642 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
642 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
412 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
642 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
