Submission #928991

#	Time	Username	Problem	Language	Result	Execution time	Memory
928991		salmon	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	1010 ms	168532 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];

int root[410][3][410];

int q(int r, int g, int y, int e){
    return root[r][0][e] + root[g][1][e] + root[y][2][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++;
        }
    }

    for(int i = 0; i < N; i++){
        root[R][0][i] = 0;
        root[G][0][i] = 0;
        root[Y][0][i] = 0;
    }

    for(int r = R - 1; r >= 0; r--){
        for(int i = 0; i < N; i++){
            root[r][0][i] = root[r + 1][0][i];
            if(i >= rp[r]) root[r][0][i]++;
        }
    }

    for(int g = G - 1; g >= 0; g--){
        for(int i = 0; i < N; i++){
            root[g][1][i] = root[g + 1][1][i];
            if(i >= gp[g]) root[g][1][i]++;
        }
    }

    for(int y = Y - 1; y >= 0; y--){
        for(int i = 0; i < N; i++){
            root[y][2][i] = root[y + 1][2][i];
            if(i >= yp[y]) root[y][2][i]++;
        }
    }

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

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