#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;
const int INF = 0x3f3f3f3f;
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
if (s[i]=='Y') pos[2].pb(i);
int R=pos[0].size()-1,G=pos[1].size()-1,Y=pos[2].size()-1;
if (R+G+Y+1<2*max({R,G,Y})) return cout<<-1<<'\n',0;
//
FOR(i,1,n)
FOR(j,0,2) {
int cnt=0;
for (auto k : pos[j]) {
if (k>i) ++cnt;
C[i][k]=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]);
cout<<MAX<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
14868 KB |
Output is correct |
7 |
Correct |
2 ms |
16888 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14876 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
12636 KB |
Output is correct |
12 |
Correct |
2 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
10588 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
14868 KB |
Output is correct |
7 |
Correct |
2 ms |
16888 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14876 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
12636 KB |
Output is correct |
12 |
Correct |
2 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
10588 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
11 ms |
55900 KB |
Output is correct |
19 |
Correct |
5 ms |
45788 KB |
Output is correct |
20 |
Correct |
7 ms |
59996 KB |
Output is correct |
21 |
Correct |
6 ms |
47808 KB |
Output is correct |
22 |
Correct |
6 ms |
53852 KB |
Output is correct |
23 |
Correct |
5 ms |
41564 KB |
Output is correct |
24 |
Correct |
3 ms |
25180 KB |
Output is correct |
25 |
Correct |
1 ms |
2396 KB |
Output is correct |
26 |
Correct |
1 ms |
2396 KB |
Output is correct |
27 |
Correct |
7 ms |
64180 KB |
Output is correct |
28 |
Correct |
6 ms |
51800 KB |
Output is correct |
29 |
Correct |
6 ms |
53848 KB |
Output is correct |
30 |
Correct |
4 ms |
41560 KB |
Output is correct |
31 |
Correct |
4 ms |
37468 KB |
Output is correct |
32 |
Correct |
5 ms |
43608 KB |
Output is correct |
33 |
Correct |
1 ms |
2396 KB |
Output is correct |
34 |
Correct |
0 ms |
2396 KB |
Output is correct |
35 |
Correct |
6 ms |
56028 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 |
35512 KB |
Output is correct |
39 |
Correct |
5 ms |
45660 KB |
Output is correct |
40 |
Correct |
1 ms |
2396 KB |
Output is correct |
41 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
146 ms |
645092 KB |
Output is correct |
3 |
Correct |
76 ms |
646192 KB |
Output is correct |
4 |
Correct |
76 ms |
648168 KB |
Output is correct |
5 |
Correct |
73 ms |
649552 KB |
Output is correct |
6 |
Correct |
72 ms |
652712 KB |
Output is correct |
7 |
Correct |
72 ms |
652004 KB |
Output is correct |
8 |
Correct |
72 ms |
653860 KB |
Output is correct |
9 |
Correct |
78 ms |
651704 KB |
Output is correct |
10 |
Correct |
74 ms |
652884 KB |
Output is correct |
11 |
Correct |
74 ms |
656724 KB |
Output is correct |
12 |
Correct |
32 ms |
314460 KB |
Output is correct |
13 |
Correct |
48 ms |
462160 KB |
Output is correct |
14 |
Correct |
66 ms |
603732 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
8540 KB |
Output is correct |
5 |
Correct |
2 ms |
12636 KB |
Output is correct |
6 |
Correct |
2 ms |
14868 KB |
Output is correct |
7 |
Correct |
2 ms |
16888 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14876 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
12636 KB |
Output is correct |
12 |
Correct |
2 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
10588 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
11 ms |
55900 KB |
Output is correct |
19 |
Correct |
5 ms |
45788 KB |
Output is correct |
20 |
Correct |
7 ms |
59996 KB |
Output is correct |
21 |
Correct |
6 ms |
47808 KB |
Output is correct |
22 |
Correct |
6 ms |
53852 KB |
Output is correct |
23 |
Correct |
5 ms |
41564 KB |
Output is correct |
24 |
Correct |
3 ms |
25180 KB |
Output is correct |
25 |
Correct |
1 ms |
2396 KB |
Output is correct |
26 |
Correct |
1 ms |
2396 KB |
Output is correct |
27 |
Correct |
7 ms |
64180 KB |
Output is correct |
28 |
Correct |
6 ms |
51800 KB |
Output is correct |
29 |
Correct |
6 ms |
53848 KB |
Output is correct |
30 |
Correct |
4 ms |
41560 KB |
Output is correct |
31 |
Correct |
4 ms |
37468 KB |
Output is correct |
32 |
Correct |
5 ms |
43608 KB |
Output is correct |
33 |
Correct |
1 ms |
2396 KB |
Output is correct |
34 |
Correct |
0 ms |
2396 KB |
Output is correct |
35 |
Correct |
6 ms |
56028 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 |
35512 KB |
Output is correct |
39 |
Correct |
5 ms |
45660 KB |
Output is correct |
40 |
Correct |
1 ms |
2396 KB |
Output is correct |
41 |
Correct |
1 ms |
2392 KB |
Output is correct |
42 |
Correct |
1 ms |
6488 KB |
Output is correct |
43 |
Correct |
146 ms |
645092 KB |
Output is correct |
44 |
Correct |
76 ms |
646192 KB |
Output is correct |
45 |
Correct |
76 ms |
648168 KB |
Output is correct |
46 |
Correct |
73 ms |
649552 KB |
Output is correct |
47 |
Correct |
72 ms |
652712 KB |
Output is correct |
48 |
Correct |
72 ms |
652004 KB |
Output is correct |
49 |
Correct |
72 ms |
653860 KB |
Output is correct |
50 |
Correct |
78 ms |
651704 KB |
Output is correct |
51 |
Correct |
74 ms |
652884 KB |
Output is correct |
52 |
Correct |
74 ms |
656724 KB |
Output is correct |
53 |
Correct |
32 ms |
314460 KB |
Output is correct |
54 |
Correct |
48 ms |
462160 KB |
Output is correct |
55 |
Correct |
66 ms |
603732 KB |
Output is correct |
56 |
Correct |
1 ms |
2396 KB |
Output is correct |
57 |
Correct |
1 ms |
2396 KB |
Output is correct |
58 |
Correct |
60 ms |
406868 KB |
Output is correct |
59 |
Correct |
69 ms |
486956 KB |
Output is correct |
60 |
Correct |
68 ms |
466436 KB |
Output is correct |
61 |
Correct |
64 ms |
443760 KB |
Output is correct |
62 |
Correct |
1 ms |
2392 KB |
Output is correct |
63 |
Correct |
79 ms |
649556 KB |
Output is correct |
64 |
Correct |
87 ms |
640444 KB |
Output is correct |
65 |
Correct |
75 ms |
605776 KB |
Output is correct |
66 |
Correct |
59 ms |
451920 KB |
Output is correct |
67 |
Correct |
55 ms |
396628 KB |
Output is correct |
68 |
Correct |
63 ms |
456020 KB |
Output is correct |
69 |
Correct |
62 ms |
449800 KB |
Output is correct |
70 |
Correct |
64 ms |
460248 KB |
Output is correct |
71 |
Correct |
68 ms |
474452 KB |
Output is correct |
72 |
Correct |
1 ms |
2396 KB |
Output is correct |
73 |
Correct |
0 ms |
2396 KB |
Output is correct |