Submission #1010230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010230		ivan_alexeev	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	198 ms	29836 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>

/*
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi2,fma,popcnt")
*/

#ifdef lisie_bimbi
#define debug(x) cout << #x << " : " << x << endl;
#else
#define debug(x) ;
#define endl '\n'
#endif

//#define int long long
#define inf 1000000000
#define double long double
typedef long long ll;

struct yeei{
    int r;
    int g;
    int y;
};

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n;
    cin >> n;
    string s;
    cin >> s;
    int r = 0, g = 0, y = 0;
    vector<int> vr, vg, vy;
    for(int i = 0; i < n; i++){
        if(s[i] == 'R'){
            r++;
            vr.push_back(i);
        }else if(s[i] == 'G'){
            g++;
            vg.push_back(i);
        }else{
            y++;
            vy.push_back(i);
        }
    }
    vector<vector<vector<yeei>>> dp(r + 1, vector<vector<yeei>>(g + 1, vector<yeei>(y + 1, {inf, inf, inf})));
    dp[0][0][0] = {0, 0, 0};
    for(int r1 = 0; r1 <= r; r1++){
        for(int g1 = 0; g1 <= g; g1++){
            for(int y1 = 0; y1 <= y; y1++){
                if((r1 == 0) && (g1 == 0) && (y1 == 0)){
                    continue;
                }
                if(r1 != 0){
                    int x = vr[r1 - 1];
                    int cnt = g1 + y1;
                    cnt -= min(g1, (int)(std::lower_bound(vg.begin(), vg.end(), x) - vg.begin()));
                    cnt -= min(y1, (int)(std::lower_bound(vy.begin(), vy.end(), x) - vy.begin()));
                    dp[r1][g1][y1].r = min(dp[r1][g1][y1].r, dp[r1 - 1][g1][y1].g + cnt);
                    dp[r1][g1][y1].r = min(dp[r1][g1][y1].r, dp[r1 - 1][g1][y1].y + cnt);
                }

                if(g1 != 0){
                    int x = vg[g1 - 1];
                    int cnt = r1 + y1;
                    cnt -= min(r1, (int)(std::lower_bound(vr.begin(), vr.end(), x) - vr.begin()));
                    cnt -= min(y1, (int)(std::lower_bound(vy.begin(), vy.end(), x) - vy.begin()));
                    dp[r1][g1][y1].g = min(dp[r1][g1][y1].g, dp[r1][g1 - 1][y1].r + cnt);
                    dp[r1][g1][y1].g = min(dp[r1][g1][y1].g, dp[r1][g1 - 1][y1].y + cnt);
                }
                if(y1 != 0){
                    int x = vy[y1 - 1];
                    int cnt = g1 + r1;
                    cnt -= min(g1, (int)(std::lower_bound(vg.begin(), vg.end(), x) - vg.begin()));
                    cnt -= min(r1, (int)(std::lower_bound(vr.begin(), vr.end(), x) - vr.begin()));
                    dp[r1][g1][y1].y = min(dp[r1][g1][y1].y, dp[r1][g1][y1 - 1].g + cnt);
                    dp[r1][g1][y1].y = min(dp[r1][g1][y1].y, dp[r1][g1][y1 - 1].r + cnt);
                }

            }
        }
    }
    int x = min(dp[r][g][y].r, min(dp[r][g][y].g, dp[r][g][y].y));
    if(x < inf){
        cout << x;
    }else{
        cout << -1;
    }
    return 0;
}

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