Submission #929022

#	Time	Username	Problem	Language	Result	Execution time	Memory
929022		salmon	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	249 ms	242508 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

int N;
int memo[3][410][410][410];
int rp[410],gp[410],yp[410];
int R;
int G;
int Y;
char lst[410];
const int inf = 1100100100;
bool visited[410];

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


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[0][R][G][Y] = 0;
    memo[1][R][G][Y] = 0;
    memo[2][R][G][Y] = 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[0][R][i] = 0;
        root[0][G][i] = 0;
        root[0][Y][i] = 0;
    }

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

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

    for(int y = Y - 1; y >= 0; y--){
        for(int i = 0; i <= N; i++){
            root[2][y][i] = root[2][y + 1][i];
            if(i >= yp[y]) root[2][y][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++){
                int y = i - r - g;
                    int j = r + g + y;

                    if(r == R || min(memo[1][r + 1][g][y], memo[2][r + 1][g][y]) == inf){
                        memo[0][r][g][y] = inf;
                    }
                    else{
                        memo[0][r][g][y] = min(memo[1][r + 1][g][y], memo[2][r + 1][g][y]) + j-rp[r]+root[0][r+1][rp[r]] + root[1][g][rp[r]] + root[2][y][rp[r]];
                    }

                    if(g == G || min(memo[0][r][g + 1][y], memo[2][r][g + 1][y]) == inf){
                        memo[1][r][g][y] = inf;
                    }
                    else{
                        memo[1][r][g][y] = min(memo[0][r][g + 1][y], memo[2][r][g + 1][y])+ j-gp[g]+root[0][r][gp[g]] + root[1][g+1][gp[g]] + root[2][y][gp[g]];
                    }

                    if(y == Y || min(memo[0][r][g][y + 1], memo[1][r][g][y + 1]) == inf){
                        memo[2][r][g][y] = inf;
                    }
                    else{
                        memo[2][r][g][y] = min(memo[0][r][g][y + 1], memo[1][r][g][y + 1])+ j-yp[y]+root[0][r][yp[y]] + root[1][g][yp[y]] + root[2][y+1][yp[y]];
                    }
            }
        }
    }

    if(min(memo[0][0][0][0],min(memo[1][0][0][0],memo[2][0][0][0])) != inf){
        printf("%d",min(memo[0][0][0][0],min(memo[1][0][0][0],memo[2][0][0][0])));
    }
    else{
        printf("-1");
    }

}
/*
6
GGGGRRR
GRGRGRG

RGRGYG
*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf(" %c",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

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