#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
vector<int>a,b,c;
vector<vector<vector<vector<int>>>>dp;
int f(int x,int y,int z,int t){
if(x==a.size() && y==b.size() && z==c.size())return 0;
if(dp[x][y][z][t]!=-1)return dp[x][y][z][t];
int mn=1e15;
if(x!=a.size() && t!=1){
int ind=upper_bound(all(b),a[x])-b.begin();
ind=min(ind,y);
int ind2=upper_bound(all(c),a[x])-c.begin();
ind2=min(ind2,z);
mn=min(mn,f(x+1,y,z,1)+y-ind+z-ind2);
}
if(y!=b.size() && t!=2){
int ind=upper_bound(all(a),b[y])-a.begin();
ind=min(ind,x);
int ind2=upper_bound(all(c),b[y])-c.begin();
ind2=min(ind2,z);
mn=min(mn,f(x,y+1,z,2)+x-ind+z-ind2);
}
if(z!=c.size() && t!=3){
int ind=upper_bound(all(a),c[z])-a.begin();
ind=min(ind,x);
int ind2=upper_bound(all(b),c[z])-b.begin();
ind2=min(ind2,y);
mn=min(mn,f(x,y,z+1,3)+x-ind+y-ind2);
}
return dp[x][y][z][t]=mn;
}
int32_t main(){
fast;
int n;
cin>>n;
string s;
cin>>s;
for(int i=0;i<n;i++){
if(s[i]=='R'){
a.pb(i);
}
if(s[i]=='G'){
b.pb(i);
}
if(s[i]=='Y'){
c.pb(i);
}
}
dp.assign((int)a.size()+5,vector<vector<vector<int>>>((int)b.size()+5,vector<vector<int>>((int)c.size()+5,vector<int>(4,-1))));
int ans=f(0,0,0,1);
if(ans==1e15)cout<<-1<<endl;
else cout<<ans<<endl;
}
Compilation message
joi2019_ho_t3.cpp: In function 'long long int f(long long int, long long int, long long int, long long int)':
joi2019_ho_t3.cpp:16:6: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if(x==a.size() && y==b.size() && z==c.size())return 0;
| ~^~~~~~~~~~
joi2019_ho_t3.cpp:16:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if(x==a.size() && y==b.size() && z==c.size())return 0;
| ~^~~~~~~~~~
joi2019_ho_t3.cpp:16:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if(x==a.size() && y==b.size() && z==c.size())return 0;
| ~^~~~~~~~~~
joi2019_ho_t3.cpp:19:6: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | if(x!=a.size() && t!=1){
| ~^~~~~~~~~~
joi2019_ho_t3.cpp:26:6: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if(y!=b.size() && t!=2){
| ~^~~~~~~~~~
joi2019_ho_t3.cpp:33:6: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if(z!=c.size() && t!=3){
| ~^~~~~~~~~~
| # |
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 |
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 |
- |
