Submission #1237756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237756		Geforgs	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	462 ms	1114112 KiB

joi2019_ho_t3

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
//#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

ll calc(ll end, ll red, ll green, ll yellow, vector<vector<vector<vector<ll>>>>& dp, vector<ll>& r, vector<ll>& g, vector<ll>& y, vector<ll>& R, vector<ll>& G, vector<ll>& Y){
    if(dp[end][red][green][yellow] != -1) return dp[end][red][green][yellow];
    int x, cnt;
    if(end == 0){
        if(red == 0){
            dp[end][red][green][yellow] = inf;
        }else{
            x = R[red-1];
            cnt = 0;
            if(r[x] > red) cnt += r[x] - red;
            if(g[x] > green) cnt += g[x] - green;
            if(y[x] > yellow) cnt += y[x] - yellow;
            dp[end][red][green][yellow] = calc(1, red-1, green, yellow, dp, r, g, y, R, G, Y) + cnt;
            dp[end][red][green][yellow] = min(dp[end][red][green][yellow], calc(2, red-1, green, yellow, dp, r, g, y, R, G, Y) + cnt);
        }
    }else if(end == 1){
        if(green == 0){
            dp[end][red][green][yellow] = inf;
        }else{
            x = G[green-1];
            cnt = 0;
            if(r[x] > red) cnt += r[x] - red;
            if(g[x] > green) cnt += g[x] - green;
            if(y[x] > yellow) cnt += y[x] - yellow;
            dp[end][red][green][yellow] = calc(0, red, green-1, yellow, dp, r, g, y, R, G, Y) + cnt;
            dp[end][red][green][yellow] = min(dp[end][red][green][yellow], calc(2, red, green-1, yellow, dp, r, g, y, R, G, Y) + cnt);
        }
    }else{
        if(yellow == 0){
            dp[end][red][green][yellow] = inf;
        }else{
            x = Y[yellow-1];
            cnt = 0;
            if(r[x] > red) cnt += r[x] - red;
            if(g[x] > green) cnt += g[x] - green;
            if(y[x] > yellow) cnt += y[x] - yellow;
            dp[end][red][green][yellow] = calc(0, red, green, yellow-1, dp, r, g, y, R, G, Y) + cnt;
            dp[end][red][green][yellow] = min(dp[end][red][green][yellow], calc(1, red, green, yellow-1, dp, r, g, y, R, G, Y) + cnt);
        }
    }
    return dp[end][red][green][yellow];
}

void solve(){
    ll n, i, k;
    string s;
    cin>>n>>s;
    k = (n+1)/2;
    vector<ll> r(n);
    vector<ll> g(n);
    vector<ll> y(n);
    vector<ll> R;
    vector<ll> G;
    vector<ll> Y;
    vector<vector<vector<vector<ll>>>> dp(3, vector<vector<vector<ll>>>(n+1, vector<vector<ll>>(n+1, vector<ll>(n+1, -1))));
    if(s[0] == 'R'){
        r[0] = 1;
        R.pb(0);
    }else if(s[0] == 'G'){
        g[0] = 1;
        G.pb(0);
    }else{
        y[0] = 1;
        Y.pb(0);
    }
    for(i=1;i<n;++i){
        r[i] = r[i-1];
        g[i] = g[i-1];
        y[i] = y[i-1];
        if(s[i] == 'R'){
            ++r[i];
            R.pb(i);
        }else if(s[i] == 'G'){
            ++g[i];
            G.pb(i);
        }else{
            ++y[i];
            Y.pb(i);
        }
    }
    if(R.size() > k or Y.size() > k or G.size() > k){
        cout<<-1<<endl;
        return;
    }
    dp[0][0][0][0] = 0;
    dp[1][0][0][0] = 0;
    dp[2][0][0][0] = 0;
    cout<<min({calc(0, R.size(), G.size(), Y.size(), dp, r, g, y, R, G, Y), calc(1, R.size(), G.size(), Y.size(), dp, r, g, y, R, G, Y), calc(2, R.size(), G.size(), Y.size(), dp, r, g, y, R, G, Y)});
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

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