Submission #1322548

#TimeUsernameProblemLanguageResultExecution timeMemory
1322548Roumak77Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
60 / 100
959 ms1114112 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {

    ll n;
    cin >> n;
    
    string s;
    cin >> s;
    
    ll r = 0, g = 0, y = 0;
    o_set<ll> R;
    o_set<ll> G;
    o_set<ll> Y;
    for(ll j = 0; j < n; j++){
        char i = s[j];
        if(i == 'R'){
            r++;
            R.insert(j);
        }else if(i == 'G'){
            g++;
            G.insert(j);
        }else if(i == 'Y'){
            y++;
            Y.insert(j);
        }
    }
    
    if(max(max(r, g), y) > (n + 1)/2){
        cout << -1 << endl;
        return 0;
    }
    
    if(n == 1){
        cout << 0 << endl;
        return 0;
    }
    
    //ll dp[n + 5][n + 5][n + 5][3]; // {0, 1, 2} = {R, G, Y}
    vector<vector<vector<vector<ll>>>> dp(n + 5LL, vector<vector<vector<ll>>>(n + 5LL, vector<vector<ll>>(n + 5LL, {(ll)1e17, (ll)1e17, (ll)1e17})));
    
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    
    for(ll i = 1; i <= n; i++){
        for(ll number_r = 0; number_r <= min(i, r); number_r++){
            
            for(ll number_g = 0; number_g <= min(i - number_r, g); number_g++){
                
                ll number_y = i - number_g - number_r;
                if(number_y > y){
                    continue;
                }
                
                
                if(number_r > 0){
                    
                    ll prev = min(dp[number_r - 1][number_g][number_y][1], dp[number_r - 1][number_g][number_y][2]);
                    
                    ll t = *R.find_by_order(number_r - 1LL);
                    ll temp = t;
                    
                    temp -= min((ll)(G.order_of_key(t)), number_g);
                    temp -= min((ll)(Y.order_of_key(t)), number_y);
                    
                    temp -= number_r - 1;
                   
                    
                    
                    
                    dp[number_r][number_g][number_y][0] = min(prev + temp, dp[number_r][number_g][number_y][0]);
                    
                }
                
                if(number_g > 0){
                    
                    ll prev = min(dp[number_r][number_g - 1][number_y][0], dp[number_r][number_g - 1][number_y][2]);
                    
                    ll t = *G.find_by_order(number_g - 1LL);
                    ll temp = t;
                    
                    temp -= min((ll)(R.order_of_key(t)), number_r);
                    temp -= min((ll)(Y.order_of_key(t)), number_y);
                    temp -= number_g - 1;
                    
                    dp[number_r][number_g][number_y][1] = min(prev + temp, dp[number_r][number_g][number_y][1]);
                    
                }
                
                if(number_y > 0){
                    
                    ll prev = min(dp[number_r][number_g][number_y - 1][0], dp[number_r][number_g][number_y - 1][1]);
                    
                    ll t = *Y.find_by_order(number_y - 1LL);
                    ll temp = t;
                    
                    temp -= min((ll)(R.order_of_key(t)), number_r);
                    temp -= min((ll)(G.order_of_key(t)), number_g);
                    temp -= number_y - 1;
                    
                    dp[number_r][number_g][number_y][2] = min(prev + temp, dp[number_r][number_g][number_y][2]);
                    
                }
                
                
            }
        }
    }
    
   

    ll ans = 1e17;
    
    
    for(auto i : dp[r][g][y]){
        ans = min(i, ans);
    }
    cout << ans;
    cout << endl;
    
    
    
    
    
    


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...