Submission #1266083

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

joi2019_ho_t3

#include <bits/stdc++.h>

const int MAXN = 401;

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

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

struct Fenwick{
    int n;
    std::vector<int> t;
    Fenwick(int n):n(n){
        t.resize(n + 1);
    }
    void upd(int i,int x){
        i++;
        for(;i<=n;i+=(i & (-i)))t[i] += x;
    }
    int sum(int i){
        i++;
        int ans =0 ;
        for(;i>0;i-=(i & (-i)))ans += t[i];
        return ans;
    }
    int sum(int l,int r){
        return sum(r) - sum(l - 1);
    }
};

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    std::string str;
    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] = std::min(dp[i][j][z][0],dp[i - 1][j][z][1] + tmp);
                    dp[i][j][z][0] = std::min(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] = std::min(dp[i][j][z][1],dp[i][j - 1][z][0] + tmp);
                    dp[i][j][z][1]  =std::min(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] = std::min(dp[i][j][z][2],dp[i][j][z - 1][0] + tmp);
                    dp[i][j][z][2] = std::min(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