#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll int
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[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 j=0; j<=4; j++)
dp[a][b][c][j]=1e18;
}
}
}
dp[0][0][0][1]=0;
dp[0][0][0][0]=0;
dp[0][0][0][2]=0;
for(ll c=0; c<=m[2]; c++)
{
for(ll a=0; a<=m[0]; a++)
{
for(ll b=0; b<=m[1]; b++)
{ll i=a+b+c;
if(c<=m[2]&&c>=0)
{
ll xx=0,yy=0,zz=0;
ll mx;
mx=(d[2][c+1]);
xx=max(0,c-o[2][mx]);
yy=max(0,b-o[1][mx]);
zz=max(0,a-o[0][mx]);
dp[a][b][c+1][2]=min(dp[a][b][c+1][2],dp[a][b][c][0]+abs(d[2][c+1]+xx+yy+zz-i));
dp[a][b][c+1][2]=min(dp[a][b][c+1][2],dp[a][b][c][1]+abs(d[2][c+1]+xx+yy+zz-i));
mx=(d[1][b+1]);
xx=max(0,c-o[2][mx]);
yy=max(0,b-o[1][mx]);
zz=max(0,a-o[0][mx]);
dp[a][b+1][c][1]=min(dp[a][b+1][c][1],dp[a][b][c][0]+abs(d[1][b+1]+xx+yy+zz-i));
dp[a][b+1][c][1]=min(dp[a][b+1][c][1],dp[a][b][c][2]+abs(d[1][b+1]+xx+yy+zz-i));
mx=(d[0][a+1]);
xx=max(0,c-o[2][mx]);
yy=max(0,b-o[1][mx]);
zz=max(0,a-o[0][mx]);
dp[a+1][b][c][0]=min(dp[a+1][b][c][0],dp[a][b][c][2]+abs(d[0][a+1]+xx+yy+zz-i));
dp[a+1][b][c][0]=min(dp[a+1][b][c][0],dp[a][b][c][1]+abs(d[0][a+1]+xx+yy+zz-i));
//}
}
}
}
}
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[m[0]][m[1]][m[2]][0],dp[m[0]][m[1]][m[2]][1],dp[m[0]][m[1]][m[2]][2]})==1e18)cout<<-1;
else
cout<<min({dp[m[0]][m[1]][m[2]][0],dp[m[0]][m[1]][m[2]][1],dp[m[0]][m[1]][m[2]][2]});
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:65:40: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
65 | dp[a][b][c][j]=1e18;
| ^~~~
joi2019_ho_t3.cpp:115:20: warning: unused variable 'c' [-Wunused-variable]
115 | ll c=i-a-b;
| ^
joi2019_ho_t3.cpp:35:8: warning: unused variable 'arr' [-Wunused-variable]
35 | ll arr[n];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
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 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
