Submission #1266087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266087		dima2101	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	295 ms	757576 KiB

joi2019_ho_t3

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

const int MAXN = 401;

int dp[MAXN][MAXN][MAXN][3];

int help[3][3][MAXN];


signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    

    int n;
    std::cin>>n;

    
    std::string s;
    std::cin >> s;
    
    std::vector<std::vector<int>> all_ind(3);

    for(int i =0 ;i < s.size();i++){
        if(s[i] == 'R'){
            all_ind[0].push_back(i);
            for(int j = 0;j < 3;j++){
                help[j][0][all_ind[0].size() - 1] = all_ind[j].size();
            }
        }else if(s[i] == 'G'){
            all_ind[1].push_back(i);
            for(int j = 0;j < 3;j++){
                help[j][1][all_ind[1].size() - 1] = all_ind[j].size();
            }
        }else{
            all_ind[2].push_back(i);
            for(int j = 0;j < 3;j++){
                help[j][2][all_ind[2].size() - 1] = all_ind[j].size();
            }
        }
    }
    // std::cout<<help[0][1][0]<<std::endl;

   
    for(int  i=0 ;i < MAXN;i++){
        for(int j =0;j < MAXN;j++){
            for(int z = 0;z < MAXN;z++){
                for(int k =0 ;k < 3;k++){
                    dp[i][j][z][k] = 1e8;
                }
            }
        }
    }
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for(int i = 0;i <= all_ind[0].size();i++){
        for(int j =0 ;j <= all_ind[1].size();j++){
            for(int z = 0;z <= all_ind[2].size();z++){
                if(i == 0 && j == 0 && z == 0)continue;
                if(i > 0){
                    int tmp = (help[1][0][i - 1] <= (j) ? -(help[1][0][i - 1] - (j)) : 0) + 
                    (help[2][0][i - 1] <= (z) ? -(help[2][0][i - 1] - (z)) : 0); 
                    dp[i][j][z][0] = dp[i - 1][j][z][1] + tmp;
                    dp[i][j][z][0] = dp[i][j][z][0] < dp[i - 1][j][z][2] + tmp ? dp[i][j][z][0] : dp[i - 1][j][z][2] + tmp;
                }
                if(j > 0){
                    int tmp = (help[0][1][j - 1] <= (i) ? -(help[0][1][j - 1] - (i)) : 0) + 
                    (help[2][1][j - 1] <= (z) ? -(help[2][1][j - 1] - (z)) : 0);
                    dp[i][j][z][1] = dp[i][j - 1][z][0] + tmp;
                    dp[i][j][z][1] = dp[i][j][z][1] < dp[i][j - 1][z][2] + tmp ? dp[i][j][z][1] : dp[i][j - 1][z][2] + tmp;
                }
                if(z > 0){
                    int tmp = (help[0][2][z - 1] <= (i) ? -(help[0][2][z - 1] - (i)) : 0) + 
                    (help[1][2][z - 1] <= (j) ? -(help[1][2][z - 1] - (j)) : 0);
                    dp[i][j][z][2] = dp[i][j][z - 1][0] + tmp;
                    dp[i][j][z][2] = dp[i][j][z][2] < dp[i][j][z - 1][1] + tmp ? dp[i][j][z][2] : dp[i][j][z - 1][1] + tmp;
                }
                // std::cout<<i<<' '<<j<<' '<<z<<' '<<dp[i][j][z][0]<<' '<<dp[i][j][z][1]<<' '<<dp[i][j][z][2]<<std::endl;
            }
        }
    }

    int best = std::min(dp[all_ind[0].size()][all_ind[1].size()][all_ind[2].size()][0],
    dp[all_ind[0].size()][all_ind[1].size()][all_ind[2].size()][1]);
    best = std::min(best,dp[all_ind[0].size()][all_ind[1].size()][all_ind[2].size()][2]);
    if(best > 1e6){
        std::cout<<-1;
    }else{
        std::cout<<best;
    }
}

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