#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FOD(i,a,b) for (int i=(a);i>=(b);i--)
#define bit(x,y) ((x)>>(y))&1
#define pb push_back
#define ll long long
#define ii pair < int,int >
#define f first
#define s second
#define M 1000000007
#define N 405
using namespace std;
const int INF = 0x3f3f3f3f;
int n;
string s;
int F[N][N][N][3];
vector < int > pos[3];
int C[N][N];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
cin>>s;
s='*'+s;
FOR(i,0,2) pos[i].pb(0);
FOR(i,1,n)
if (s[i]=='R') pos[0].pb(i);
else
if (s[i]=='G') pos[1].pb(i);
else
if (s[i]=='Y') pos[2].pb(i);
int R=pos[0].size()-1,G=pos[1].size()-1,Y=pos[2].size()-1;
if (R+G+Y<=2*max({R,G,Y})) return cout<<-1<<'\n',0;
//
FOR(i,1,n)
FOR(j,0,2) {
int cnt=0;
for (auto k : pos[j]) {
if (k>i) ++cnt;
C[i][k]=cnt;
}
}
//
FOR(i,0,n) C[0][i]=0;
//
memset(F,+INF,sizeof(F));
int MAX=INT_MAX;
FOR(i,0,2) F[0][0][0][i]=0;
FOR(i,0,R)
FOR(j,0,G)
FOR(k,0,Y) {
if (i>0) F[i][j][k][0]=min(F[i-1][j][k][1],F[i-1][j][k][2])+C[pos[0][i]][pos[1][j]]+C[pos[0][i]][pos[2][k]];
if (j>0) F[i][j][k][1]=min(F[i][j-1][k][0],F[i][j-1][k][2])+C[pos[1][j]][pos[0][i]]+C[pos[1][j]][pos[2][k]];
if (k>0) F[i][j][k][2]=min(F[i][j][k-1][0],F[i][j][k-1][1])+C[pos[2][k]][pos[0][i]]+C[pos[2][k]][pos[1][j]];
}
FOR(i,0,2) MAX=min(MAX,F[R][G][Y][i]);
cout<<MAX<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
