#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <memory.h>
#include <cmath>
#include <array>
using namespace std;
void re(int& x);
void re(char* c);
void pr(int x);
void pr(const char *x);
void ps();
template<class T, class... Ts> void ps(const T& t, const Ts&... ts);
#ifdef FFDBG
#else
#define dbg(x...) dsfdsfsdfasd
#endif
void re(int& x) { scanf("%d", &x); }
void re(char* c) { scanf("%s", c); }
void pr(int x) { printf("%d", x); }
void pr(const char *x) { printf("%s", x); }
void ps() { pr("\n"); }
template<class T, class... Ts> void ps(const T& t, const Ts&... ts) {
pr(t); if (sizeof...(ts)) pr(" "); ps(ts...);
}
#define rep(i, a, b) for(int i = a; i < (b); ++i)
int n;
char s[500];
vector<int> locs[3];
int ct[3][410];
int dp[410][410][410][3];
int sn[410][410][410][3];
int rec(int l1, int l2, int l3, int p) {
//dbg(l1,l2,l3,p);
if (l1+l2+l3==n) return 0;
int l[3] = {l1,l2,l3};
int &ret = dp[l1][l2][l3][p];
if (!sn[l1][l2][l3][p]) {
sn[l1][l2][l3][p]=1;
ret = 1000000000;
for (int nxt = 0; nxt < 3; nxt++) if ((l1+l2+l3 ==0||nxt != p) && l[nxt] != locs[nxt].size()) {
int this_pos = locs[nxt][l[nxt]];
int hm = -1;
for (int ot = 0; ot < 3; ot++) {
hm += max(0, ct[ot][this_pos] - l[ot]);
}
l[nxt]++;
//dbg(l1,l2,l3,p,nxt,hm);
ret = min(ret, hm + rec(l[0],l[1],l[2],nxt));
l[nxt]--;
}
}
return ret;
}
void solve()
{
re(n);
re(s);
rep(i,0,n) {
if (i!=0) rep(j,0,3) ct[j][i] = ct[j][i-1];
if (s[i]=='R') {
locs[0].push_back(i);
ct[0][i]++;
}
else if (s[i]=='G') {
ct[1][i]++;
locs[1].push_back(i);
}
else {
ct[2][i]++;
locs[2].push_back(i);
}
}
int ans = rec(0,0,0,0);
ps(ans == 1000000000 ? -1 : ans);
}
int main() {
solve();
}
Compilation message
joi2019_ho_t3.cpp: In function 'int rec(int, int, int, int)':
joi2019_ho_t3.cpp:65:82: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int nxt = 0; nxt < 3; nxt++) if ((l1+l2+l3 ==0||nxt != p) && l[nxt] != locs[nxt].size()) {
~~~~~~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void re(int&)':
joi2019_ho_t3.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void re(int& x) { scanf("%d", &x); }
~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void re(char*)':
joi2019_ho_t3.cpp:34:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void re(char* c) { scanf("%s", c); }
~~~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
632 KB |
Output is correct |
6 |
Correct |
5 ms |
632 KB |
Output is correct |
7 |
Correct |
5 ms |
632 KB |
Output is correct |
8 |
Correct |
5 ms |
636 KB |
Output is correct |
9 |
Correct |
5 ms |
632 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
632 KB |
Output is correct |
12 |
Correct |
5 ms |
632 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
632 KB |
Output is correct |
6 |
Correct |
5 ms |
632 KB |
Output is correct |
7 |
Correct |
5 ms |
632 KB |
Output is correct |
8 |
Correct |
5 ms |
636 KB |
Output is correct |
9 |
Correct |
5 ms |
632 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
632 KB |
Output is correct |
12 |
Correct |
5 ms |
632 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
7 ms |
4216 KB |
Output is correct |
19 |
Correct |
7 ms |
3448 KB |
Output is correct |
20 |
Correct |
7 ms |
4088 KB |
Output is correct |
21 |
Correct |
7 ms |
4344 KB |
Output is correct |
22 |
Correct |
6 ms |
2936 KB |
Output is correct |
23 |
Correct |
7 ms |
3832 KB |
Output is correct |
24 |
Correct |
6 ms |
2808 KB |
Output is correct |
25 |
Correct |
5 ms |
1400 KB |
Output is correct |
26 |
Correct |
5 ms |
1656 KB |
Output is correct |
27 |
Correct |
7 ms |
4344 KB |
Output is correct |
28 |
Correct |
8 ms |
4472 KB |
Output is correct |
29 |
Correct |
7 ms |
4088 KB |
Output is correct |
30 |
Correct |
7 ms |
4088 KB |
Output is correct |
31 |
Correct |
7 ms |
3576 KB |
Output is correct |
32 |
Correct |
7 ms |
4216 KB |
Output is correct |
33 |
Correct |
5 ms |
1912 KB |
Output is correct |
34 |
Correct |
6 ms |
2424 KB |
Output is correct |
35 |
Correct |
7 ms |
4344 KB |
Output is correct |
36 |
Correct |
7 ms |
3448 KB |
Output is correct |
37 |
Correct |
7 ms |
3064 KB |
Output is correct |
38 |
Correct |
7 ms |
3704 KB |
Output is correct |
39 |
Correct |
7 ms |
4216 KB |
Output is correct |
40 |
Correct |
5 ms |
504 KB |
Output is correct |
41 |
Correct |
5 ms |
1400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
8 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6648 KB |
Output is correct |
4 |
Correct |
8 ms |
6648 KB |
Output is correct |
5 |
Correct |
8 ms |
6652 KB |
Output is correct |
6 |
Correct |
9 ms |
6648 KB |
Output is correct |
7 |
Correct |
8 ms |
6648 KB |
Output is correct |
8 |
Correct |
8 ms |
6648 KB |
Output is correct |
9 |
Correct |
8 ms |
6648 KB |
Output is correct |
10 |
Correct |
8 ms |
6648 KB |
Output is correct |
11 |
Correct |
8 ms |
6648 KB |
Output is correct |
12 |
Correct |
6 ms |
3576 KB |
Output is correct |
13 |
Correct |
7 ms |
4728 KB |
Output is correct |
14 |
Correct |
8 ms |
5624 KB |
Output is correct |
15 |
Correct |
8 ms |
6648 KB |
Output is correct |
16 |
Correct |
8 ms |
6652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
632 KB |
Output is correct |
6 |
Correct |
5 ms |
632 KB |
Output is correct |
7 |
Correct |
5 ms |
632 KB |
Output is correct |
8 |
Correct |
5 ms |
636 KB |
Output is correct |
9 |
Correct |
5 ms |
632 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
632 KB |
Output is correct |
12 |
Correct |
5 ms |
632 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
7 ms |
4216 KB |
Output is correct |
19 |
Correct |
7 ms |
3448 KB |
Output is correct |
20 |
Correct |
7 ms |
4088 KB |
Output is correct |
21 |
Correct |
7 ms |
4344 KB |
Output is correct |
22 |
Correct |
6 ms |
2936 KB |
Output is correct |
23 |
Correct |
7 ms |
3832 KB |
Output is correct |
24 |
Correct |
6 ms |
2808 KB |
Output is correct |
25 |
Correct |
5 ms |
1400 KB |
Output is correct |
26 |
Correct |
5 ms |
1656 KB |
Output is correct |
27 |
Correct |
7 ms |
4344 KB |
Output is correct |
28 |
Correct |
8 ms |
4472 KB |
Output is correct |
29 |
Correct |
7 ms |
4088 KB |
Output is correct |
30 |
Correct |
7 ms |
4088 KB |
Output is correct |
31 |
Correct |
7 ms |
3576 KB |
Output is correct |
32 |
Correct |
7 ms |
4216 KB |
Output is correct |
33 |
Correct |
5 ms |
1912 KB |
Output is correct |
34 |
Correct |
6 ms |
2424 KB |
Output is correct |
35 |
Correct |
7 ms |
4344 KB |
Output is correct |
36 |
Correct |
7 ms |
3448 KB |
Output is correct |
37 |
Correct |
7 ms |
3064 KB |
Output is correct |
38 |
Correct |
7 ms |
3704 KB |
Output is correct |
39 |
Correct |
7 ms |
4216 KB |
Output is correct |
40 |
Correct |
5 ms |
504 KB |
Output is correct |
41 |
Correct |
5 ms |
1400 KB |
Output is correct |
42 |
Correct |
5 ms |
380 KB |
Output is correct |
43 |
Correct |
8 ms |
6648 KB |
Output is correct |
44 |
Correct |
8 ms |
6648 KB |
Output is correct |
45 |
Correct |
8 ms |
6648 KB |
Output is correct |
46 |
Correct |
8 ms |
6652 KB |
Output is correct |
47 |
Correct |
9 ms |
6648 KB |
Output is correct |
48 |
Correct |
8 ms |
6648 KB |
Output is correct |
49 |
Correct |
8 ms |
6648 KB |
Output is correct |
50 |
Correct |
8 ms |
6648 KB |
Output is correct |
51 |
Correct |
8 ms |
6648 KB |
Output is correct |
52 |
Correct |
8 ms |
6648 KB |
Output is correct |
53 |
Correct |
6 ms |
3576 KB |
Output is correct |
54 |
Correct |
7 ms |
4728 KB |
Output is correct |
55 |
Correct |
8 ms |
5624 KB |
Output is correct |
56 |
Correct |
8 ms |
6648 KB |
Output is correct |
57 |
Correct |
8 ms |
6652 KB |
Output is correct |
58 |
Correct |
281 ms |
147832 KB |
Output is correct |
59 |
Correct |
290 ms |
181368 KB |
Output is correct |
60 |
Correct |
291 ms |
169248 KB |
Output is correct |
61 |
Correct |
306 ms |
164600 KB |
Output is correct |
62 |
Correct |
16 ms |
17912 KB |
Output is correct |
63 |
Correct |
24 ms |
31480 KB |
Output is correct |
64 |
Correct |
90 ms |
100984 KB |
Output is correct |
65 |
Correct |
152 ms |
144120 KB |
Output is correct |
66 |
Correct |
290 ms |
166648 KB |
Output is correct |
67 |
Correct |
276 ms |
159096 KB |
Output is correct |
68 |
Correct |
290 ms |
171328 KB |
Output is correct |
69 |
Correct |
298 ms |
165624 KB |
Output is correct |
70 |
Correct |
287 ms |
177016 KB |
Output is correct |
71 |
Correct |
273 ms |
161016 KB |
Output is correct |
72 |
Correct |
25 ms |
21624 KB |
Output is correct |
73 |
Correct |
8 ms |
4728 KB |
Output is correct |