#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll visited[405][405][405][3];
ll dp[405][405][405][3];
ll tr,tg,ty,tt;
ll rr[405],gg[405],yy[405],r2[405],g2[405],y2[405];
ll dp2(ll r,ll g,ll y,ll last){
if (visited[r][g][y][last]==1) return dp[r][g][y][last];
visited[r][g][y][last] = 1;
if (r+g+y==1){
return 0;
}
ll ind,temp;
ll ar=r,ag=g,ay=y;
if (last==0){
ind = rr[tr-r+1];
temp = abs(r+g+y-1-ind+max(tg-g-g2[ind],0)+max(ty-y-y2[ind],0));
ar--;
}
else if (last==1){
ind = gg[tg-g+1];
temp = abs(r+g+y-1-ind+max(tr-r-r2[ind],0)+max(ty-y-y2[ind],0));
ag--;
}
else{
ind = yy[ty-y+1];
temp = abs(r+g+y-1-ind+max(tg-g-g2[ind],0)+max(tr-r-r2[ind],0));
ay--;
}
ll ans1=1000000,ans2=1000000,ans3=1000000;
if (ar>0 && last!=0) ans1 = dp2(ar,ag,ay,0)+temp;
if (ag>0 && last!=1) ans2 = dp2(ar,ag,ay,1)+temp;
if (ay>0 && last!=2) ans3 = dp2(ar,ag,ay,2)+temp;
ll ans = min(min(ans1,ans2),ans3);
dp[r][g][y][last] = ans;
// cout << r << " " << g << " " << y << " " << last << " " << ans << " " << ind << "\n";
return ans;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll t;
t=1;
while (t--){
ll n;
cin >> n;
string s;
cin >> s;
ll r1=1,g1=1,y1=1;
rr[0] = n,gg[0]=n,yy[0]=n;
for (int i=n-1;i>=0;i--){
if (s[i]=='R') {
rr[r1] = i;
r1++;
}
else if (s[i]=='G') {
gg[g1] = i;
g1++;
}
else {
yy[y1] = i;
y1++;
}
r2[i] = r1-1;
g2[i] = g1-1;
y2[i] = y1-1;
}
tr = r1-1;
ty = y1-1;
tg = g1-1;
tt = n;
ll ans1=1000000,ans2=1000000,ans3=1000000;
if (tr>0) ans1 = dp2(tr,tg,ty,0);
if (tg>0) ans2 = dp2(tr,tg,ty,1);
if (ty>0) ans3 = dp2(tr,tg,ty,2);
ll ans = min(min(ans1,ans2),ans3);
if (ans<500000) cout << ans;
else cout << -1;
// dp2(0,1,1,1);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
356 KB |
Output is correct |
4 |
Correct |
1 ms |
6612 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
12888 KB |
Output is correct |
9 |
Correct |
2 ms |
12904 KB |
Output is correct |
10 |
Correct |
2 ms |
12760 KB |
Output is correct |
11 |
Correct |
2 ms |
10712 KB |
Output is correct |
12 |
Correct |
2 ms |
10844 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
12892 KB |
Output is correct |
15 |
Correct |
1 ms |
8796 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
356 KB |
Output is correct |
4 |
Correct |
1 ms |
6612 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
12888 KB |
Output is correct |
9 |
Correct |
2 ms |
12904 KB |
Output is correct |
10 |
Correct |
2 ms |
12760 KB |
Output is correct |
11 |
Correct |
2 ms |
10712 KB |
Output is correct |
12 |
Correct |
2 ms |
10844 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
12892 KB |
Output is correct |
15 |
Correct |
1 ms |
8796 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
9 ms |
47452 KB |
Output is correct |
19 |
Correct |
5 ms |
39004 KB |
Output is correct |
20 |
Correct |
7 ms |
51548 KB |
Output is correct |
21 |
Correct |
7 ms |
41560 KB |
Output is correct |
22 |
Correct |
7 ms |
48988 KB |
Output is correct |
23 |
Correct |
5 ms |
35164 KB |
Output is correct |
24 |
Correct |
4 ms |
22364 KB |
Output is correct |
25 |
Correct |
6 ms |
46004 KB |
Output is correct |
26 |
Correct |
10 ms |
60508 KB |
Output is correct |
27 |
Correct |
7 ms |
55644 KB |
Output is correct |
28 |
Correct |
7 ms |
43356 KB |
Output is correct |
29 |
Correct |
6 ms |
45404 KB |
Output is correct |
30 |
Correct |
6 ms |
35160 KB |
Output is correct |
31 |
Correct |
5 ms |
32860 KB |
Output is correct |
32 |
Correct |
5 ms |
37212 KB |
Output is correct |
33 |
Correct |
6 ms |
50456 KB |
Output is correct |
34 |
Correct |
6 ms |
44632 KB |
Output is correct |
35 |
Correct |
7 ms |
47492 KB |
Output is correct |
36 |
Correct |
6 ms |
41048 KB |
Output is correct |
37 |
Correct |
4 ms |
28508 KB |
Output is correct |
38 |
Correct |
5 ms |
30812 KB |
Output is correct |
39 |
Correct |
6 ms |
39256 KB |
Output is correct |
40 |
Correct |
1 ms |
604 KB |
Output is correct |
41 |
Correct |
3 ms |
19292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
51 ms |
216296 KB |
Output is correct |
3 |
Correct |
29 ms |
218460 KB |
Output is correct |
4 |
Correct |
28 ms |
220328 KB |
Output is correct |
5 |
Correct |
30 ms |
220512 KB |
Output is correct |
6 |
Correct |
30 ms |
220252 KB |
Output is correct |
7 |
Correct |
29 ms |
218192 KB |
Output is correct |
8 |
Correct |
29 ms |
216400 KB |
Output is correct |
9 |
Correct |
28 ms |
214352 KB |
Output is correct |
10 |
Correct |
28 ms |
216424 KB |
Output is correct |
11 |
Correct |
29 ms |
216208 KB |
Output is correct |
12 |
Correct |
25 ms |
201040 KB |
Output is correct |
13 |
Correct |
27 ms |
208220 KB |
Output is correct |
14 |
Correct |
27 ms |
208976 KB |
Output is correct |
15 |
Correct |
28 ms |
210276 KB |
Output is correct |
16 |
Correct |
29 ms |
210260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
356 KB |
Output is correct |
4 |
Correct |
1 ms |
6612 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
12892 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
12888 KB |
Output is correct |
9 |
Correct |
2 ms |
12904 KB |
Output is correct |
10 |
Correct |
2 ms |
12760 KB |
Output is correct |
11 |
Correct |
2 ms |
10712 KB |
Output is correct |
12 |
Correct |
2 ms |
10844 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
12892 KB |
Output is correct |
15 |
Correct |
1 ms |
8796 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
9 ms |
47452 KB |
Output is correct |
19 |
Correct |
5 ms |
39004 KB |
Output is correct |
20 |
Correct |
7 ms |
51548 KB |
Output is correct |
21 |
Correct |
7 ms |
41560 KB |
Output is correct |
22 |
Correct |
7 ms |
48988 KB |
Output is correct |
23 |
Correct |
5 ms |
35164 KB |
Output is correct |
24 |
Correct |
4 ms |
22364 KB |
Output is correct |
25 |
Correct |
6 ms |
46004 KB |
Output is correct |
26 |
Correct |
10 ms |
60508 KB |
Output is correct |
27 |
Correct |
7 ms |
55644 KB |
Output is correct |
28 |
Correct |
7 ms |
43356 KB |
Output is correct |
29 |
Correct |
6 ms |
45404 KB |
Output is correct |
30 |
Correct |
6 ms |
35160 KB |
Output is correct |
31 |
Correct |
5 ms |
32860 KB |
Output is correct |
32 |
Correct |
5 ms |
37212 KB |
Output is correct |
33 |
Correct |
6 ms |
50456 KB |
Output is correct |
34 |
Correct |
6 ms |
44632 KB |
Output is correct |
35 |
Correct |
7 ms |
47492 KB |
Output is correct |
36 |
Correct |
6 ms |
41048 KB |
Output is correct |
37 |
Correct |
4 ms |
28508 KB |
Output is correct |
38 |
Correct |
5 ms |
30812 KB |
Output is correct |
39 |
Correct |
6 ms |
39256 KB |
Output is correct |
40 |
Correct |
1 ms |
604 KB |
Output is correct |
41 |
Correct |
3 ms |
19292 KB |
Output is correct |
42 |
Correct |
1 ms |
4440 KB |
Output is correct |
43 |
Correct |
51 ms |
216296 KB |
Output is correct |
44 |
Correct |
29 ms |
218460 KB |
Output is correct |
45 |
Correct |
28 ms |
220328 KB |
Output is correct |
46 |
Correct |
30 ms |
220512 KB |
Output is correct |
47 |
Correct |
30 ms |
220252 KB |
Output is correct |
48 |
Correct |
29 ms |
218192 KB |
Output is correct |
49 |
Correct |
29 ms |
216400 KB |
Output is correct |
50 |
Correct |
28 ms |
214352 KB |
Output is correct |
51 |
Correct |
28 ms |
216424 KB |
Output is correct |
52 |
Correct |
29 ms |
216208 KB |
Output is correct |
53 |
Correct |
25 ms |
201040 KB |
Output is correct |
54 |
Correct |
27 ms |
208220 KB |
Output is correct |
55 |
Correct |
27 ms |
208976 KB |
Output is correct |
56 |
Correct |
28 ms |
210276 KB |
Output is correct |
57 |
Correct |
29 ms |
210260 KB |
Output is correct |
58 |
Correct |
171 ms |
297384 KB |
Output is correct |
59 |
Correct |
198 ms |
327764 KB |
Output is correct |
60 |
Correct |
190 ms |
321256 KB |
Output is correct |
61 |
Correct |
181 ms |
314208 KB |
Output is correct |
62 |
Correct |
33 ms |
234068 KB |
Output is correct |
63 |
Correct |
40 ms |
242140 KB |
Output is correct |
64 |
Correct |
73 ms |
296760 KB |
Output is correct |
65 |
Correct |
104 ms |
313044 KB |
Output is correct |
66 |
Correct |
180 ms |
320848 KB |
Output is correct |
67 |
Correct |
172 ms |
296800 KB |
Output is correct |
68 |
Correct |
178 ms |
326292 KB |
Output is correct |
69 |
Correct |
187 ms |
320396 KB |
Output is correct |
70 |
Correct |
183 ms |
324508 KB |
Output is correct |
71 |
Correct |
179 ms |
324944 KB |
Output is correct |
72 |
Correct |
33 ms |
202052 KB |
Output is correct |
73 |
Correct |
2 ms |
10844 KB |
Output is correct |