Submission #960263

#	Time	Username	Problem	Language	Result	Execution time	Memory
960263		LCJLY	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	60 / 100	151 ms	325968 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
//typedef pair<pii,pii>pi2;
typedef array<int,6>pi2;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
string s;
vector<int>v[3];
int arr[100];

int f(int color, int pos){
	int hold=lower_bound(v[color].begin(),v[color].end(),pos)-v[color].begin();
	return hold;	
}

int add(int a, int b){
	return  max(0LL,a+b);	
}

int memo[61][61][61][61][3];

int dp(int index, int r, int g, int b,int last){
	if(index==n) return 0;
	if(memo[index][r][g][b][last]!=-1) return memo[index][r][g][b][last];
	int ans=1e15;
	
	if(index==0){
		//put red
		if(r<(int)v[0].size())ans=min(ans,dp(index+1,r+1,g,b,0)+v[0][r]);
		
		//put green
		if(g<(int)v[1].size())ans=min(ans,dp(index+1,r,g+1,b,1)+v[1][g]);
		
		//put blue
		if(g<(int)v[2].size())ans=min(ans,dp(index+1,r,g,b+1,2)+v[2][b]);
	}
	else{
		//put red
		if(r<(int)v[0].size() && last!=0){
			int hold=f(1,v[0][r]);
			int hold2=f(2,v[0][r]);
			
			int cost=add(hold,-g)+add(hold2,-b);
			
			ans=min(ans,dp(index+1,r+1,g,b,0)+cost);
		}
		
		//put green
		if(g<(int)v[1].size() && last!=1){
			int hold=f(0,v[1][g]);
			int hold2=f(2,v[1][g]);
			
			int cost=add(hold,-r)+add(hold2,-b);
			
			ans=min(ans,dp(index+1,r,g+1,b,1)+cost);
		}
		
		//put blue
		if(b<(int)v[2].size() && last!=2){
			int hold=f(0,v[2][b]);
			int hold2=f(1,v[2][b]);
			
			int cost=add(hold,-r)+add(hold2,-g);
			
			ans=min(ans,dp(index+1,r,g,b+1,2)+cost);
		}
	}
	return memo[index][r][g][b][last]=ans;
}

void solve(){
	cin >> n >> s;
	
	for(int x=0;x<n;x++){
		if(s[x]=='R'){
			arr[x]=0;
		}
		else if(s[x]=='G'){
			arr[x]=1;
		}
		else arr[x]=2;
		v[arr[x]].push_back(x);
	}
	
	memset(memo,-1,sizeof(memo));
	int hold=dp(0,0,0,0,0);
	if(hold>=1e10){
		cout << -1;
	}
	else cout << hold;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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