#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,nr[3],f[405][405][405][3],r,g,y,R,G,Y,s;
vector<pair<int,pair<int,int> > >v[3];
char c;
int get(char c)
{
if(c=='R')return 0;
if(c=='G')return 1;
return 2;
}
int cst(pair<int,pair<int,int> >x,pair<int,pair<int,int> >y)
{
return abs(x.fr-y.fr)+abs(x.sc.fr-y.sc.fr)+abs(x.sc.sc-y.sc.sc);
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>c;
nr[get(c)]++;
v[get(c)].pb({nr[0],{nr[1],nr[2]}});
}
R=v[0].size(),G=v[1].size(),Y=v[2].size();
if(max(max(R,G),Y)>(n+1)/2)rc(-1);
for(r=0;r<=R;r++)
{
for(g=0;g<=G;g++)
{
for(y=0;y<=Y;y++)
{
f[r][g][y][0]=f[r][g][y][1]=f[r][g][y][2]=inf;
s=r+g+y;
if(!s)continue;
if(r)
{
f[r][g][y][0]=min(f[r-1][g][y][1],f[r-1][g][y][2])+cst(v[0][r-1],{r,{g,y}});
}
if(g)
{
f[r][g][y][1]=min(f[r][g-1][y][0],f[r][g-1][y][2])+cst(v[1][g-1],{r,{g,y}});
}
if(y)
{
f[r][g][y][2]=min(f[r][g][y-1][0],f[r][g][y-1][1])+cst(v[2][y-1],{r,{g,y}});
}
}
}
}
cout<<min(min(f[R][G][Y][0],f[R][G][Y][1]),f[R][G][Y][2])/2<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
