Submission #928958

#	Time	Username	Problem	Language	Result	Execution time	Memory
928958		oolimry	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	628 ms	170088 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]; 
  
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:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf(" %c",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

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