#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
using namespace std;
namespace __gnu_pbds
{
typedef tree<ll,
null_type,
less_equal<ll>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
#define fi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define ll double
#define ll1 long long
#define F first
#define S second
#define sz size()
#define all(s) s.begin(),s.end()
#define all1(s) s.rbegin(),s.rend()
int main()
{
//freopen("stdin.in","r",stdin);freopen("stdout.out","w",stdout);
//cin>>T;ll oo=0;
ll n;
cin>>n;
string s;
cin>>s;
map<ll,ll>m;
map<ll,map<ll,ll>>d;
ll arr[n];
ll o[3][n];
o[0][0]=0;
o[1][0]=0;
o[2][0]=0;
for(ll i=0; i<n; i++)
{
ll a=0;
if(s[i]=='R')a=0;
else if(s[i]=='G')a=1;
else a=2;
m[a]++;
d[a][m[a]]=i;
if(i)
{
o[0][i]=o[0][i-1];
o[1][i]=o[1][i-1];
o[2][i]=o[2][i-1];
}
o[a][i]+=1;
}
ll dp[n+5][m[0]+5][m[1]+5][m[2]+5][5];
for(ll a=0; a<=m[0]+4; a++)
{
for(ll b=0; b<=m[1]+4; b++)
{
for(ll c=0; c<=m[2]+4; c++)
{
for(ll i=0; i<=n+4; i++)
{
for(ll j=0; j<=4; j++)
dp[i][a][b][c][j]=1e18;
}
}
}
}
dp[0][0][0][0][1]=0;
dp[0][0][0][0][0]=0;
dp[0][0][0][0][2]=0;
for(ll i=0; i<n; i++)
{
for(ll a=0; a<=m[0]; a++)
{
for(ll b=0; b<=m[1]; b++)
{
ll c=i-a-b;
if(c<=m[2]&&c>=0)
{
// if(c<m[2])
// {
ll xx=0,yy=0,zz=0;
ll maxIndex = max(i, d[2][c+1]);
xx = min(c, o[2][maxIndex]);
if (i && d[2][c+1])
{
ll minIndex = min(i-1, d[2][c+1]-1);
xx -= (o[2][minIndex]);
}
maxIndex = max(i, d[2][c+1]);
yy = min(c, o[1][maxIndex]);
if (i && d[2][c+1])
{
ll minIndex = min(i-1, d[2][c+1]-1);
yy -= min(c, o[1][minIndex]);
}
maxIndex = max(i, d[2][c+1]);
zz = min(c, o[0][maxIndex]);
if (i && d[2][c+1])
{
ll minIndex = min(i-1, d[2][c+1]-1);
zz -= min(c, o[0][minIndex]);
}
cout<<xx<<" "<<yy<<" "<<zz<<" "<<d[2][c+1]<<" "<<i<<'\n';
dp[i+1][a][b][c+1][2]=min(dp[i+1][a][b][c+1][2],dp[i][a][b][c][0]+abs(d[2][c+1]-i-xx-yy-zz));
dp[i+1][a][b][c+1][2]=min(dp[i+1][a][b][c+1][2],dp[i][a][b][c][1]+abs(d[2][c+1]-i-xx-yy-zz));
//}
//if(b<m[1])
//{
maxIndex = max(i, d[1][b+1]);
xx = min(c, o[2][maxIndex]);
if (i && d[1][b+1])
{
ll minIndex = min(i-1, d[1][b+1]-1);
xx -= (o[2][minIndex]);
}
maxIndex = max(i, d[1][b+1]);
yy = min(c, o[1][maxIndex]);
if (i && d[1][b+1])
{
ll minIndex = min(i-1, d[1][b+1]-1);
yy -= min(c, o[1][minIndex]);
}
maxIndex = max(i, d[1][b+1]);
zz = min(c, o[0][maxIndex]);
if (i && d[1][b+1])
{
ll minIndex = min(i-1, d[1][b+1]-1);
zz -= min(c, o[0][minIndex]);
}
dp[i+1][a][b+1][c][1]=min(dp[i+1][a][b+1][c][1],dp[i][a][b][c][0]+abs(d[1][b+1]-i-xx-yy-zz));
dp[i+1][a][b+1][c][1]=min(dp[i+1][a][b+1][c][1],dp[i][a][b][c][2]+abs(d[1][b+1]-i-xx-yy-zz));
//}
//if(a<m[0])
//{
maxIndex = max(i, d[0][a+1]);
xx = min(c, o[2][maxIndex]);
if (i && d[0][a+1])
{
ll minIndex = min(i-1, d[0][a+1]-1);
xx -= (o[2][minIndex]);
}
maxIndex = max(i, d[0][a+1]);
yy = min(c, o[1][maxIndex]);
if (i && d[0][a+1])
{
ll minIndex = min(i-1, d[0][a+1]-1);
yy -= min(c, o[1][minIndex]);
}
maxIndex = max(i, d[0][a+1]);
zz = min(c, o[0][maxIndex]);
if (i && d[0][a+1])
{
ll minIndex = min(i-1, d[0][a+1]-1);
zz -= min(c, o[0][minIndex]);
}
dp[i+1][a+1][b][c][0]=min(dp[i+1][a+1][b][c][0],dp[i][a][b][c][2]+abs(d[0][a+1]-i-xx-yy-zz));
dp[i+1][a+1][b][c][0]=min(dp[i+1][a+1][b][c][0],dp[i][a][b][c][1]+abs(d[0][a+1]-i-xx-yy-zz));
//}
}
}
}
}
for(ll i=0; i<=n; i++)
{
for(ll a=0; a<=m[0]; a++)
{
for(ll b=0; b<=m[1]; b++)
{
ll c=i-a-b;
if(c<=m[2])cout<<dp[n][m[0]][m[1]][m[2]][0]<<" "<<dp[n][m[0]][m[1]][m[2]][1]<<" "<<dp[n][m[0]][m[1]][m[2]][2]<<"\n";
}
}
}
if(min({dp[n][m[0]][m[1]][m[2]][0],dp[n][m[0]][m[1]][m[2]][1],dp[n][m[0]][m[1]][m[2]][2]})==1e18)cout<<-1;
else
cout<<min({dp[n][m[0]][m[1]][m[2]][0],dp[n][m[0]][m[1]][m[2]][1],dp[n][m[0]][m[1]][m[2]][2]});
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:35:8: warning: unused variable 'arr' [-Wunused-variable]
35 | ll arr[n];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
