제출 #634025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634025		urosk	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	147 ms	130796 KiB

joi2019_ho_t3

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 1000000000 // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/

#define maxn 405
ll n;
ll a[maxn];
ll dp[maxn][maxn][maxn][4];
bool bio[maxn][maxn][maxn][4];
ll sz[4];
ll pos[4][maxn];
ll calc[4][4][maxn][maxn];
ll reshi(ll r,ll g,ll y,ll last){
    if(r+g+y==0) return 0;
    if(bio[r][g][y][last]) return dp[r][g][y][last];
    ll &ans = dp[r][g][y][last];
    bio[r][g][y][last] = 1;
    ans = llinf;
    if(r&&last!=1) ans = min(ans,reshi(r-1,g,y,1)+calc[1][2][r][g]+calc[1][3][r][y]);
    if(g&&last!=2) ans = min(ans,reshi(r,g-1,y,2)+calc[2][1][g][r]+calc[2][3][g][y]);
    if(y&&last!=3) ans = min(ans,reshi(r,g,y-1,3)+calc[3][1][y][r]+calc[3][2][y][g]);
    return ans;
}
int main(){
	daj_mi_malo_vremena
    cin >> n; string s; cin >> s;
    for(ll i = 1;i<=n;i++){
        if(s[i-1]=='R') pos[1][++sz[1]] = i;
        if(s[i-1]=='G') pos[2][++sz[2]] = i;
        if(s[i-1]=='Y') pos[3][++sz[3]] = i;
    }
    for(ll e = 1;e<=3;e++){
        for(ll f = 1;f<=3;f++){
            if(e==f) continue;
            for(ll i = 1;i<=sz[e];i++){
                ll cur = 0;
                for(ll j = sz[f];j>=1;j--){
                    calc[e][f][i][j] = cur;
                    if(pos[e][i]>pos[f][j]) cur++;
                }
                calc[e][f][i][0] = cur;
            }
        }
    }
    ll ans = llinf;
    ans = min(ans,reshi(sz[1],sz[2],sz[3],1));
    ans = min(ans,reshi(sz[1],sz[2],sz[3],2));
    ans = min(ans,reshi(sz[1],sz[2],sz[3],3));
    if(ans==llinf) ans = -1;
    cout<<ans<<endl;
	return 0;
}

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