#include <bits/stdc++.h>
using namespace std;
const int N=405;
const int inf=1e9+7;
//int dp[3][N][N],tmp[3][N][N];
int pos[3][N],cnt[3];
char s[N];
void Clear(int a[3][N][N]){ for(int i=0;i<3;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++) a[i][j][k]=inf;}
void ckmn(int &a, int b){ a=min(a,b);}
int dp[3][N][N][N];
bool was[3][N][N][N];
int Solve(int r, int g, int y, int f)
{
if(was[f][r][g][y]) return dp[f][r][g][y];
was[f][r][g][y]=1;
dp[f][r][g][y]=inf;
int i=r+g+y;
if(i==0) return dp[f][r][g][y]=0;
if(f!=0 && r) ckmn(dp[f][r][g][y],Solve(r-1,g,y,0)+max(0,pos[0][r]-i));
if(f!=1 && g) ckmn(dp[f][r][g][y],Solve(r,g-1,y,1)+max(0,pos[1][g]-i));
if(f!=2 && y) ckmn(dp[f][r][g][y],Solve(r,g,y-1,2)+max(0,pos[2][y]-i));
return dp[f][r][g][y];
}
int main()
{
int n;
scanf("%i",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
if(s[i]=='R') pos[0][++cnt[0]]=i;
if(s[i]=='G') pos[1][++cnt[1]]=i;
if(s[i]=='Y') pos[2][++cnt[2]]=i;
}
//for(int i=0;i<3;i++) reverse(pos[i]+1,pos[i]+1+cnt[i]);
int ans=min(Solve(cnt[0],cnt[1],cnt[2],0),Solve(cnt[0],cnt[1],cnt[2],1));
printf("%i\n",ans==inf?-1:ans);
/*Clear(dp);
//printf("%i %i %i\n",cnt[0],cnt[1],cnt[2]);
if(cnt[0]) dp[0][cnt[0]-1][cnt[1]]=pos[0][cnt[0]]-1;
if(cnt[1]) dp[1][cnt[0]][cnt[1]-1]=pos[1][cnt[1]]-1;
if(cnt[2]) dp[2][cnt[0]][cnt[1]]=pos[2][cnt[2]]-1;
for(int i=2;i<=n;i++)
{
Clear(tmp);
for(int f=0;f<3;f++)
for(int r=0;r<=cnt[0];r++)
for(int g=0;g<=cnt[1];g++) if(dp[f][r][g]!=inf)
{
int y=n-i-r-g+1;
//printf("%i %i %i %i: %i\n",f,r,g,y,dp[f][r][g]);
if(f!=0 && r) ckmn(tmp[0][r-1][g],dp[f][r][g]+max(0,pos[0][r]-i));
if(f!=1 && g) ckmn(tmp[1][r][g-1],dp[f][r][g]+max(0,pos[1][g]-i));
if(f!=2 && y) ckmn(tmp[2][r][g],dp[f][r][g]+max(0,pos[2][y]-i));
}
for(int f=0;f<3;f++)
for(int r=0;r<=cnt[0];r++)
for(int g=0;g<=cnt[1];g++)
dp[f][r][g]=tmp[f][r][g];
}
int ans=inf;
for(int f=0;f<3;f++) ckmn(ans,dp[f][0][0]);
printf("%i\n",ans==inf?-1:ans);*/
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s+1);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
660 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
636 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
660 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
636 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4984 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5028 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4972 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 7 |
Correct |
7 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4856 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4988 KB |
Output is correct |
| 11 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 12 |
Correct |
8 ms |
2784 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3576 KB |
Output is correct |
| 14 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 15 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 16 |
Correct |
6 ms |
4984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
660 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
636 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
