Submission #928983

#	Time	Username	Problem	Language	Result	Execution time	Memory
928983		salmon	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	60 / 100	638 ms	170048 KiB

joi2019_ho_t3

#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 (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t3.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]);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25