Submission #1332775

#TimeUsernameProblemLanguageResultExecution timeMemory
1332775developinpopGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
479 ms1114112 KiB
/*
_____________________.
|____________________|   $$\                                                            $$\           $$\        $$\               
|____________________|   $$ |                                                           \__|          $$ |       $$ |              
|____________________| $$$$$$\    $$$$$$\  $$$$$$\  $$$$$$$\   $$$$$$$\        $$$$$$\  $$\  $$$$$$\  $$$$$$$\ $$$$$$\    $$$$$$$\ 
|____________________| \_$$  _|  $$  __$$\ \____$$\ $$  __$$\ $$  _____|      $$  __$$\ $$ |$$  __$$\ $$  __$$\\_$$  _|  $$  _____|
|____________________|   $$ |    $$ |  \__|$$$$$$$ |$$ |  $$ |\$$$$$$\        $$ |  \__|$$ |$$ /  $$ |$$ |  $$ | $$ |    \$$$$$$\  
                         $$ |$$\ $$ |     $$  __$$ |$$ |  $$ | \____$$\       $$ |      $$ |$$ |  $$ |$$ |  $$ | $$ |$$\  \____$$\ 
                         \$$$$  |$$ |     \$$$$$$$ |$$ |  $$ |$$$$$$$  |      $$ |      $$ |\$$$$$$$ |$$ |  $$ | \$$$$  |$$$$$$$  |
            へ   ♡        \____/ \__|      \_______|\__|  \__|\_______/       \__|      \__| \____$$ |\__|  \__|  \____/ \_______/ 
         ૮ - ՛)                                                                             $$\   $$ |    
         / ⁻ ៸|                                                                              \$$$$$$  |   are human rights :3
     乀 (ˍ,ل ل                                                                               \______/ 
 
*/
 
#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;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<pair<T, long long>, null_type, 
                      less<pair<T, long long>>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf (ll)2e18+4
#define pb push_back
#define se second
#define fi first
#define endl '\n'
#define mp make_pair
#define pll pair<ll,ll>
#define kth_smallest find_by_order
#define num_of_smaller order_of_key
#define fori(x) for(ll i=0;i<x;i++)
#define forj(y) for(ll j=0;j<y;j++)
#define fork(z) for(ll k=0;k<z;k++)
 
#define DEBUG
 
#ifdef DEBUG
#define show(x) cerr<<#x<<" is "<<x<<endl;
#define show2(x,y) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define show3(x,y,z) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<endl;
#define show4(x,y,z,a) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<" "<<#a<<" is "<<a<<endl;
#define show_vec(a) for(auto &i:a)cerr<<i<<" ";cerr<<endl;
#define skillissue cerr<<"your code is running\n";
#define getchar_unlocked _getchar_nolock // comment before submission
#else
#define show(x)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,a)
#define show_vec(a)
#define skillissue
#endif
 
/*
 
inline int readint() {
    int x=0; char ch=getchar_unlocked(); bool s=1;
    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
    return s?x:-x;
}
 
*/


const ll maxn=403;
ll s[maxn];


ll at[3][maxn];
ll n;
ll mem[maxn][maxn][maxn][4];


//            G    Y
ll dp(ll i,ll j,ll k,ll last){
	ll l=n-i-j-k;
	if(j<0 or k<0 or l<0){return inf;}
	if(i==n)return 0;
	if(mem[i][j][k][last]!=-1)return mem[i][j][k][last];
	if(last==0)
		return mem[i][j][k][last]=min({abs(at[2][l]-i)+dp(i+1,j,k,2), abs(at[1][k]-i)+dp(i+1,j,k-1,1)});
	else if(last==1)
		return mem[i][j][k][last]=min({abs(at[2][l]-i)+dp(i+1,j,k,2), abs(at[0][j]-i)+dp(i+1,j-1,k,0)});
	else
		return mem[i][j][k][last]=min({abs(at[1][k]-i)+dp(i+1,j,k-1,1), abs(at[0][j]-i)+dp(i+1,j-1,k,0)});
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	string ss;cin>>ss;
	memset(mem,-1,sizeof(mem));
	fori(n){
		if(ss[i]=='R')s[i]=0;
		else if(ss[i]=='G')s[i]=1;
		else s[i]=2;
	}
	
	ll cnt[3];
	forj(3){
		ll c=0;
		for(ll i=n-1;i>=0;i--){
			if(s[i]==j){
				c++;
				at[j][c]=i;
			}
		}
		cnt[j]=c;
		at[j][0]=inf;
	}
	cout<<(dp(0,cnt[0],cnt[1],4)>=(1e10)?-1:dp(0,cnt[0],cnt[1],4)/2);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...