#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=405;
const int inf=8e18;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
string s;
cin>>s;
s='X'+s;
vector<int>v(n+1);
vector<vector<int>>pre(3,vector<int>(n+1,0));
vector<int>pos[3];
pos[0].pb(-1);
pos[1].pb(-1);
pos[2].pb(-1);
for(int i=1;i<=n;i++){
if(s[i]=='Y'){
v[i]=0;
}
else if(s[i]=='G'){
v[i]=1;
}
else {
v[i]=2;
}
pre[v[i]][i]=1;
for(int j=0;j<3;j++){
pre[j][i]+=pre[j][i-1];
}
pos[v[i]].pb(i);
}
vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(n+1,vector<int>(3,8e18)));
dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=0;
for(int i=1;i<=n;i++){
vector<vector<vector<int>>>dp2(n+1,vector<vector<int>>(n+1,vector<int>(3,8e18)));
for(int j=0;j<=min(i,pre[0][n]);j++){
for(int k=0;k<=min(i-j,pre[1][n]);k++){
if(i-j-k<0 or i-j-k>pre[2][n])continue;
if(j){
dp2[j][k][0]=min(max(pos[0][j]-i,0LL)+min(dp[j-1][k][1],dp[j-1][k][2]),inf);
}
if(k){
dp2[j][k][1]=min(max(pos[1][k]-i,0LL)+min(dp[j][k-1][0],dp[j][k-1][2]),inf);
}
int r=i-j-k;
if(r){
dp2[j][k][2]=min(max(pos[2][r]-i,0LL)+min(dp[j][k][0],dp[j][k][1]),inf);
}
//for(int h=0;h<3;h++)cout<<i<<' '<<j<<' '<<k<<' '<<r<<' '<<h<<' '<<dp2[j][k][h]<<'\n';
}
}swap(dp2,dp);
}
int ans=8e18;
for(int i=0;i<3;i++){
chmin(ans,dp[sz(pos[0])-1][sz(pos[1])-1][i]);
//cout<<ans<<' ';
}
if(ans>=8e18){
cout<<-1<<'\n';
}
else{
cout<<ans<<'\n';
}
}
/*
input:
dp[i][r][g][t]=dp[i-1][r-1][g]
*/
Compilation message
joi2019_ho_t3.cpp: In function 'void setIO(std::string)':
joi2019_ho_t3.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
424 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
456 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
420 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
424 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
456 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
420 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
1073 ms |
18116 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
424 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
456 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
420 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
