#include <bits/stdc++.h>
using namespace std;
int N;
int memo[410][410][410][3];
int rp[410],gp[410],yp[410];
int R;
int G;
int Y;
char lst[410];
const int inf = 1100100100;
int cost[410][410][410][3];
bool visited[410];
struct node{
int s, e, m;
node *l,*r;
int v;
node(int S, int E){
s = S;
e = E;
m = (s + e)/2;
v = 0;
l = NULL;
r = NULL;
}
node(node *root){
s = root -> s;
e = root -> e;
m = root -> m;
v = root -> v;
if(root -> l != NULL){
l = new node(root -> l);
r = new node(root -> r);
}
else{
l = NULL;
r = NULL;
}
}
void update(int i){
if(s == e){
v++;
return;
}
v++;
if(l == NULL){
l = new node(s,m);
r = new node(m + 1,e);
}
if(i <= m){
l -> update(i);
}
else{
r -> update(i);
}
}
int query(int S, int E){
if(S <= s && e <= E){
return v;
}
long long int V = 0;
if(l == NULL) return 0;
if(S <= m){
V += l -> query(S,E);
}
if(m < E){
V += r -> query(S,E);
}
return V;
}
}*root [400][3];
int q(int r, int g, int y, int s, int e){
return root[r][0] -> query(s,e) + root[g][1] -> query(s,e) + root[y][2] -> query(s,e);
}
int main(){
scanf(" %d",&N);
for(int i = 0; i < N; i++){
scanf(" %c",&lst[i]);
if(lst[i] == 'R'){
R++;
}
else if(lst[i] == 'G'){
G++;
}
else if(lst[i] == 'Y'){
Y++;
}
}
memo[R][G][Y][0] = 0;
memo[R][G][Y][1] = 0;
memo[R][G][Y][2] = 0;
int it = 0;
for(int i = 0; i < N; i++){
if(lst[i] == 'R'){
rp[it] = i;
it++;
}
}
it = 0;
for(int i = 0; i < N; i++){
if(lst[i] == 'G'){
gp[it] = i;
it++;
}
}
it = 0;
for(int i = 0; i < N; i++){
if(lst[i] == 'Y'){
yp[it] = i;
it++;
}
}
root[R][0] = new node(0,N - 1);
root[G][1] = new node(0,N-1);
root[Y][2] = new node(0,N-1);
for(int r = R - 1; r >= 0; r--){
root[r][0] = new node(root[r + 1][0]);
root[r][0] -> update(rp[r]);
}
for(int g = G - 1; g >= 0; g--){
root[g][1] = new node(root[g + 1][1]);
root[g][1] -> update(gp[g]);
}
for(int y = Y - 1; y >= 0; y--){
root[y][2] = new node(root[y + 1][2]);
root[y][2] -> update(yp[y]);
}
for(int i = N - 1; i >= 0; i--){
for(int r = 0; r <= min(R,i); r++){
for(int g = 0; g <= min(G,i - r); g++){
for(int y = 0; y <= min(Y,i - r - g); y++){
int j = r + g + y;
if(r == R || min(memo[r + 1][g][y][1], memo[r + 1][g][y][2]) == inf){
memo[r][g][y][0] = inf;
}
else{
int pos = rp[r] - q(r+1,g,y,0,rp[r]);
memo[r][g][y][0] = min(memo[r + 1][g][y][1], memo[r + 1][g][y][2]) + abs(pos-j);
}
if(g == G || min(memo[r][g + 1][y][0], memo[r][g + 1][y][2]) == inf){
memo[r][g][y][1] = inf;
}
else{
int pos = gp[g] - q(r,g+1,y,0,gp[g]);
memo[r][g][y][1] = min(memo[r][g + 1][y][0], memo[r][g + 1][y][2])+abs(pos-j);
}
if(y == Y || min(memo[r][g][y + 1][0], memo[r][g][y + 1][1]) == inf){
memo[r][g][y][2] = inf;
}
else{
int pos = yp[y] - q(r,g,y+1,0,yp[y]);
memo[r][g][y][2] = min(memo[r][g][y + 1][0], memo[r][g][y + 1][1])+abs(pos-j);
}
}
}
}
}
if(min(memo[0][0][0][0],min(memo[0][0][0][1],memo[0][0][0][2])) != inf){
printf("%d",min(memo[0][0][0][0],min(memo[0][0][0][1],memo[0][0][0][2])));
}
else{
printf("-1");
}
}
/*
6
GGGGRRR
GRGRGRG
RGRGYG
*/
Compilation message
growing.cpp: In function 'int main()':
growing.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
growing.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf(" %c",&lst[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
2648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
