#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FOD(i,a,b) for (int i=(a);i>=(b);i--)
#define bit(x,y) ((x)>>(y))&1
#define pb push_back
#define ll long long
#define ii pair < int,int >
#define f first
#define s second
#define M 1000000007
#define N 405
using namespace std;
int n;
string s;
int F[N][N][N][3];
vector < int > pos[3];
int C[N][N];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
cin>>s;
s='*'+s;
FOR(i,0,2) pos[i].pb(0);
FOR(i,1,n)
if (s[i]=='R') pos[0].pb(i);
else
if (s[i]=='G') pos[1].pb(i);
else pos[2].pb(i);
int R=pos[0].size()-1,G=pos[1].size()-1,Y=pos[2].size()-1;
//
for (auto i : pos[0]) {
int cnt=0;
for (auto j : pos[1]) {
if (j>i) ++cnt;
C[i][j]=cnt;
}
cnt=0;
for (auto j : pos[2]) {
if (j>i) ++cnt;
C[i][j]=cnt;
}
}
//
for (auto i : pos[1]) {
int cnt=0;
for (auto j : pos[0]) {
if (j>i) ++cnt;
C[i][j]=cnt;
}
cnt=0;
for (auto j : pos[2]) {
if (j>i) ++cnt;
C[i][j]=cnt;
}
}
//
for (auto i : pos[2]) {
int cnt=0;
for (auto j : pos[0]) {
if (j>i) ++cnt;
C[i][j]=cnt;
}
cnt=0;
for (auto j : pos[1]) {
if (j>i) ++cnt;
C[i][j]=cnt;
}
}
//
FOR(i,0,R)
FOR(j,0,G)
FOR(k,0,Y)
FOR(c,0,2) F[i][j][k][c]=INT_MAX;
int MAX=INT_MAX;
FOR(i,0,2) F[0][0][0][i]=0;
FOR(i,0,R)
FOR(j,0,G)
FOR(k,0,Y) {
if (i>0) F[i][j][k][0]=min(F[i-1][j][k][1],F[i-1][j][k][2])+C[pos[0][i]][pos[1][j]]+C[pos[0][i]][pos[2][k]];
if (j>0) F[i][j][k][1]=min(F[i][j-1][k][0],F[i][j-1][k][2])+C[pos[1][j]][pos[0][i]]+C[pos[1][j]][pos[2][k]];
if (k>0) F[i][j][k][2]=min(F[i][j][k-1][0],F[i][j][k-1][1])+C[pos[2][k]][pos[0][i]]+C[pos[2][k]][pos[1][j]];
}
FOR(i,0,2) MAX=min(MAX,F[R][G][Y][i]);
if (MAX==INT_MAX) return cout<<-1,0;
cout<<MAX;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
14684 KB |
Output is correct |
7 |
Correct |
2 ms |
16732 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
3 ms |
22876 KB |
Output is correct |
11 |
Correct |
2 ms |
12636 KB |
Output is correct |
12 |
Correct |
2 ms |
12828 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
10588 KB |
Output is correct |
16 |
Correct |
3 ms |
24924 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
14684 KB |
Output is correct |
7 |
Correct |
2 ms |
16732 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
3 ms |
22876 KB |
Output is correct |
11 |
Correct |
2 ms |
12636 KB |
Output is correct |
12 |
Correct |
2 ms |
12828 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
10588 KB |
Output is correct |
16 |
Correct |
3 ms |
24924 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
6 ms |
55900 KB |
Output is correct |
19 |
Correct |
5 ms |
45660 KB |
Output is correct |
20 |
Correct |
6 ms |
59996 KB |
Output is correct |
21 |
Correct |
5 ms |
47708 KB |
Output is correct |
22 |
Correct |
6 ms |
53852 KB |
Output is correct |
23 |
Correct |
5 ms |
41648 KB |
Output is correct |
24 |
Correct |
3 ms |
25180 KB |
Output is correct |
25 |
Correct |
9 ms |
88668 KB |
Output is correct |
26 |
Correct |
8 ms |
74328 KB |
Output is correct |
27 |
Correct |
7 ms |
64092 KB |
Output is correct |
28 |
Correct |
5 ms |
51804 KB |
Output is correct |
29 |
Correct |
6 ms |
53852 KB |
Output is correct |
30 |
Correct |
4 ms |
41564 KB |
Output is correct |
31 |
Correct |
4 ms |
37468 KB |
Output is correct |
32 |
Correct |
4 ms |
43612 KB |
Output is correct |
33 |
Correct |
7 ms |
59996 KB |
Output is correct |
34 |
Correct |
6 ms |
53852 KB |
Output is correct |
35 |
Correct |
6 ms |
55900 KB |
Output is correct |
36 |
Correct |
5 ms |
47708 KB |
Output is correct |
37 |
Correct |
4 ms |
33372 KB |
Output is correct |
38 |
Correct |
4 ms |
35420 KB |
Output is correct |
39 |
Correct |
5 ms |
45660 KB |
Output is correct |
40 |
Correct |
1 ms |
2648 KB |
Output is correct |
41 |
Correct |
3 ms |
25180 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
73 ms |
661004 KB |
Output is correct |
3 |
Correct |
75 ms |
659208 KB |
Output is correct |
4 |
Correct |
83 ms |
676688 KB |
Output is correct |
5 |
Correct |
79 ms |
696908 KB |
Output is correct |
6 |
Correct |
75 ms |
696852 KB |
Output is correct |
7 |
Correct |
75 ms |
694104 KB |
Output is correct |
8 |
Correct |
76 ms |
694100 KB |
Output is correct |
9 |
Correct |
76 ms |
694196 KB |
Output is correct |
10 |
Correct |
75 ms |
696912 KB |
Output is correct |
11 |
Correct |
77 ms |
694920 KB |
Output is correct |
12 |
Correct |
31 ms |
314460 KB |
Output is correct |
13 |
Correct |
46 ms |
462164 KB |
Output is correct |
14 |
Correct |
60 ms |
603732 KB |
Output is correct |
15 |
Correct |
74 ms |
696144 KB |
Output is correct |
16 |
Correct |
77 ms |
694100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
14684 KB |
Output is correct |
7 |
Correct |
2 ms |
16732 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
3 ms |
22876 KB |
Output is correct |
11 |
Correct |
2 ms |
12636 KB |
Output is correct |
12 |
Correct |
2 ms |
12828 KB |
Output is correct |
13 |
Correct |
1 ms |
8540 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
10588 KB |
Output is correct |
16 |
Correct |
3 ms |
24924 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
6 ms |
55900 KB |
Output is correct |
19 |
Correct |
5 ms |
45660 KB |
Output is correct |
20 |
Correct |
6 ms |
59996 KB |
Output is correct |
21 |
Correct |
5 ms |
47708 KB |
Output is correct |
22 |
Correct |
6 ms |
53852 KB |
Output is correct |
23 |
Correct |
5 ms |
41648 KB |
Output is correct |
24 |
Correct |
3 ms |
25180 KB |
Output is correct |
25 |
Correct |
9 ms |
88668 KB |
Output is correct |
26 |
Correct |
8 ms |
74328 KB |
Output is correct |
27 |
Correct |
7 ms |
64092 KB |
Output is correct |
28 |
Correct |
5 ms |
51804 KB |
Output is correct |
29 |
Correct |
6 ms |
53852 KB |
Output is correct |
30 |
Correct |
4 ms |
41564 KB |
Output is correct |
31 |
Correct |
4 ms |
37468 KB |
Output is correct |
32 |
Correct |
4 ms |
43612 KB |
Output is correct |
33 |
Correct |
7 ms |
59996 KB |
Output is correct |
34 |
Correct |
6 ms |
53852 KB |
Output is correct |
35 |
Correct |
6 ms |
55900 KB |
Output is correct |
36 |
Correct |
5 ms |
47708 KB |
Output is correct |
37 |
Correct |
4 ms |
33372 KB |
Output is correct |
38 |
Correct |
4 ms |
35420 KB |
Output is correct |
39 |
Correct |
5 ms |
45660 KB |
Output is correct |
40 |
Correct |
1 ms |
2648 KB |
Output is correct |
41 |
Correct |
3 ms |
25180 KB |
Output is correct |
42 |
Correct |
1 ms |
6492 KB |
Output is correct |
43 |
Correct |
73 ms |
661004 KB |
Output is correct |
44 |
Correct |
75 ms |
659208 KB |
Output is correct |
45 |
Correct |
83 ms |
676688 KB |
Output is correct |
46 |
Correct |
79 ms |
696908 KB |
Output is correct |
47 |
Correct |
75 ms |
696852 KB |
Output is correct |
48 |
Correct |
75 ms |
694104 KB |
Output is correct |
49 |
Correct |
76 ms |
694100 KB |
Output is correct |
50 |
Correct |
76 ms |
694196 KB |
Output is correct |
51 |
Correct |
75 ms |
696912 KB |
Output is correct |
52 |
Correct |
77 ms |
694920 KB |
Output is correct |
53 |
Correct |
31 ms |
314460 KB |
Output is correct |
54 |
Correct |
46 ms |
462164 KB |
Output is correct |
55 |
Correct |
60 ms |
603732 KB |
Output is correct |
56 |
Correct |
74 ms |
696144 KB |
Output is correct |
57 |
Correct |
77 ms |
694100 KB |
Output is correct |
58 |
Correct |
61 ms |
406808 KB |
Output is correct |
59 |
Correct |
66 ms |
486740 KB |
Output is correct |
60 |
Correct |
66 ms |
466228 KB |
Output is correct |
61 |
Correct |
65 ms |
443728 KB |
Output is correct |
62 |
Correct |
82 ms |
700088 KB |
Output is correct |
63 |
Correct |
80 ms |
688020 KB |
Output is correct |
64 |
Correct |
82 ms |
679252 KB |
Output is correct |
65 |
Correct |
75 ms |
605888 KB |
Output is correct |
66 |
Correct |
61 ms |
451924 KB |
Output is correct |
67 |
Correct |
58 ms |
396436 KB |
Output is correct |
68 |
Correct |
62 ms |
456020 KB |
Output is correct |
69 |
Correct |
69 ms |
449872 KB |
Output is correct |
70 |
Correct |
64 ms |
460112 KB |
Output is correct |
71 |
Correct |
66 ms |
474700 KB |
Output is correct |
72 |
Correct |
72 ms |
675408 KB |
Output is correct |
73 |
Correct |
2 ms |
12888 KB |
Output is correct |