#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const ll inf = (1ll<<60);
const int iinf=2147483647;
const ll mod = 998244353;
const ll maxn=405;
const double PI=acos(-1);
ll pw(ll x, ll p, ll m=mod){
ll ret=1;
while (p>0){
if (p&1){
ret*=x;
ret%=m;
}
x*=x;
x%=m;
p>>=1;
}
return ret;
}
ll inv(ll a, ll m=mod){
return pw(a,m-2);
}
int dp[maxn][maxn][maxn][3];
int pos[3][maxn];
int cnt[3][maxn];
signed main(){
IOS();
int n; cin>>n;
string str; cin>>str;
str='$'+str;
int tota=0, totb=0, totc=0;
REP1(i,n){
if (str[i]=='R') tota++;
else if (str[i]=='G') totb++;
else totc++;
}
REP(i,maxn){
REP(j,maxn){
REP(k,maxn){
REP(l, 3){
dp[i][j][k][l]=inf;
}
}
}
}
REP1(i,n){
REP(l, 3) cnt[l][i]=cnt[l][i-1];
if (str[i]=='R') {
cnt[0][i]++;
pos[0][cnt[0][i]]=i;
}
else if (str[i]=='G') {
cnt[1][i]++;
pos[1][cnt[1][i]]=i;
}
else {
cnt[2][i]++;
pos[2][cnt[2][i]]=i;
}
}
dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
// 0 is R, 1 is G, 2 is Y
REP(i, tota+1){
REP(j, totb+1){
REP(k, totc+1){
if (i+j+k==0) continue;
if (i>0){
int p=pos[0][i]-1;
dp[i][j][k][0]=min(dp[i-1][j][k][1], dp[i-1][j][k][2]);
dp[i][j][k][0]+=p-min(i-1, cnt[0][p])-min(j, cnt[1][p])-min(k, cnt[2][p]);
}
if (j>0){
int p=pos[1][j]-1;
dp[i][j][k][1]=min(dp[i][j-1][k][0], dp[i][j-1][k][2]);
dp[i][j][k][1]+=p-min(i, cnt[0][p])-min(j-1, cnt[1][p])-min(k, cnt[2][p]);
}
if (k>0){
int p=pos[2][k]-1;
dp[i][j][k][2]=min(dp[i][j][k-1][0], dp[i][j][k-1][1]);
dp[i][j][k][2]+=p-min(i, cnt[0][p])-min(j, cnt[1][p])-min(k-1, cnt[2][p]);
}
}
}
}
int k=min({dp[tota][totb][totc][0], dp[tota][totb][totc][1], dp[tota][totb][totc][2]});
if (k==inf) k=-1;
cout<<k<<endl;
}
/*
3
YYG
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
631 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
631 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
475 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
631 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
