#include <iostream>
#include <fstream>
using namespace std;
const int nmax=405;
int dp[2][nmax][nmax][3];
int ap[3],nr[3];
int p[3][nmax][3],a[3][nmax];
int n,i,j,k,use,oth,ch,nxt,ans;
string s;
int norm(char c)
{
if(c=='R') return 0;
if(c=='G') return 1;
return 2;
}
int actual_pos(int wh)
{
int ret=a[wh][ap[wh]];
for(int oth=0;oth<3;oth++)
if(oth!=wh)
ret+=max(0,ap[oth]-p[wh][ap[wh]][oth]);
return ret;
}
void prp(int &a,int b)
{
a=min(a,b);
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
cin>>s;s=" "+s;
for(i=1;i<=n;i++)
a[norm(s[i])][++nr[norm(s[i])]]=i;
for(i=0;i<3;i++)
for(j=1;j<=nr[i];j++)
for(oth=0;oth<3;oth++)
{
while(p[i][j][oth]<=nr[oth]&&a[oth][p[i][j][oth]]<a[i][j])
p[i][j][oth]++;
p[i][j][oth]--;
}
for(i=0;i<2;i++)
for(j=0;j<=n;j++)
for(k=0;k<=n;k++)
for(ch=0;ch<3;ch++)
dp[i][j][k][ch]=(1<<30);
for(i=0;i<3;i++)
dp[0][0][0][i]=0;
for(i=1;i<=n;i++)
{
use=1-use;
for(j=0;j<=i-1;j++)
for(k=0;k<=i-1-j;k++)
for(ch=0;ch<3;ch++)
{
ap[0]=j;ap[1]=k;ap[2]=i-1-j-k;
for(nxt=0;nxt<3;nxt++)
if(nxt!=ch&&ap[nxt]<nr[nxt])
{
ap[nxt]++;
prp(dp[use][ap[0]][ap[1]][nxt],dp[1-use][j][k][ch]+actual_pos(nxt)-i);
ap[nxt]--;
}
}
for(j=0;j<=i;j++)
for(k=0;k<=i-j;k++)
for(ch=0;ch<3;ch++)
{
dp[1-use][j][k][ch]=(1<<30);
}
}
ans=(1<<30);
for(i=0;i<3;i++)
ans=min(ans,dp[use][nr[0]][nr[1]][i]);
if(ans==(1<<30)) ans=-1;
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
5 ms |
896 KB |
Output is correct |
19 |
Correct |
4 ms |
896 KB |
Output is correct |
20 |
Correct |
5 ms |
1024 KB |
Output is correct |
21 |
Correct |
5 ms |
896 KB |
Output is correct |
22 |
Correct |
4 ms |
896 KB |
Output is correct |
23 |
Correct |
4 ms |
896 KB |
Output is correct |
24 |
Correct |
6 ms |
896 KB |
Output is correct |
25 |
Correct |
4 ms |
896 KB |
Output is correct |
26 |
Correct |
5 ms |
896 KB |
Output is correct |
27 |
Correct |
4 ms |
896 KB |
Output is correct |
28 |
Correct |
6 ms |
896 KB |
Output is correct |
29 |
Correct |
5 ms |
896 KB |
Output is correct |
30 |
Correct |
6 ms |
896 KB |
Output is correct |
31 |
Correct |
3 ms |
896 KB |
Output is correct |
32 |
Correct |
5 ms |
896 KB |
Output is correct |
33 |
Correct |
5 ms |
896 KB |
Output is correct |
34 |
Correct |
4 ms |
896 KB |
Output is correct |
35 |
Correct |
4 ms |
896 KB |
Output is correct |
36 |
Correct |
6 ms |
896 KB |
Output is correct |
37 |
Correct |
5 ms |
896 KB |
Output is correct |
38 |
Correct |
4 ms |
896 KB |
Output is correct |
39 |
Correct |
6 ms |
896 KB |
Output is correct |
40 |
Correct |
6 ms |
896 KB |
Output is correct |
41 |
Correct |
5 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
450 ms |
4204 KB |
Output is correct |
3 |
Correct |
485 ms |
4224 KB |
Output is correct |
4 |
Correct |
495 ms |
4344 KB |
Output is correct |
5 |
Execution timed out |
560 ms |
4316 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
5 ms |
896 KB |
Output is correct |
19 |
Correct |
4 ms |
896 KB |
Output is correct |
20 |
Correct |
5 ms |
1024 KB |
Output is correct |
21 |
Correct |
5 ms |
896 KB |
Output is correct |
22 |
Correct |
4 ms |
896 KB |
Output is correct |
23 |
Correct |
4 ms |
896 KB |
Output is correct |
24 |
Correct |
6 ms |
896 KB |
Output is correct |
25 |
Correct |
4 ms |
896 KB |
Output is correct |
26 |
Correct |
5 ms |
896 KB |
Output is correct |
27 |
Correct |
4 ms |
896 KB |
Output is correct |
28 |
Correct |
6 ms |
896 KB |
Output is correct |
29 |
Correct |
5 ms |
896 KB |
Output is correct |
30 |
Correct |
6 ms |
896 KB |
Output is correct |
31 |
Correct |
3 ms |
896 KB |
Output is correct |
32 |
Correct |
5 ms |
896 KB |
Output is correct |
33 |
Correct |
5 ms |
896 KB |
Output is correct |
34 |
Correct |
4 ms |
896 KB |
Output is correct |
35 |
Correct |
4 ms |
896 KB |
Output is correct |
36 |
Correct |
6 ms |
896 KB |
Output is correct |
37 |
Correct |
5 ms |
896 KB |
Output is correct |
38 |
Correct |
4 ms |
896 KB |
Output is correct |
39 |
Correct |
6 ms |
896 KB |
Output is correct |
40 |
Correct |
6 ms |
896 KB |
Output is correct |
41 |
Correct |
5 ms |
1024 KB |
Output is correct |
42 |
Correct |
2 ms |
384 KB |
Output is correct |
43 |
Correct |
450 ms |
4204 KB |
Output is correct |
44 |
Correct |
485 ms |
4224 KB |
Output is correct |
45 |
Correct |
495 ms |
4344 KB |
Output is correct |
46 |
Execution timed out |
560 ms |
4316 KB |
Time limit exceeded |
47 |
Halted |
0 ms |
0 KB |
- |