Submission #960268

#	Time	Username	Problem	Language	Result	Execution time	Memory
960268		LCJLY	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	2 ms	7772 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[401];
int memo2[3][401];
int dp[2][401][401][3];

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

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

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(memo2,-1,sizeof(memo2));
	
	//iterative
	for(int x=0;x<401;x++){
		for(int y=0;y<401;y++){
			for(int i=0;i<3;i++){
				dp[0][x][y][i]=1e15;
				dp[1][x][y][i]=1e15;
			}
		}
	}
	
	dp[0][0][0][0]=0;
	
	for(int r=0;r<(int)v[0].size();r++){
		for(int g=0;g<(int)v[1].size();g++){
			for(int b=0;b<(int)v[2].size();b++){
				for(int last=0;last<3;last++){
					int index=r+g+b;
					
					if(index==0){
						dp[1][g][b][0]=min(dp[1][g][b][0],dp[0][g][b][last]+v[0][r]);
						
						dp[0][g+1][b][1]=min(dp[0][g+1][b][1],dp[0][g][b][last]+v[1][g]);
						
						dp[0][g][b+1][2]=min(dp[0][g][b+1][2],dp[0][g][b][last]+v[2][b]);
					}	
					else{
						if(last!=0){
							int hold=f(1,v[0][r]);
							int hold2=f(2,v[0][r]);
							
							int cost=add(hold,-g)+add(hold2,-b);
							
							dp[1][g][b][0]=min(dp[1][g][b][0],dp[0][g][b][last]+cost);
						}
						
						if(last!=1){
							int hold=f(0,v[1][g]);
							int hold2=f(2,v[1][g]);
							
							int cost=add(hold,-r)+add(hold2,-b);
							
							dp[0][g+1][b][1]=min(dp[0][g+1][b][1],dp[0][g][b][last]+cost);
						}
						
						if(last!=2){
							int hold=f(0,v[2][b]);
							int hold2=f(1,v[2][b]);
							
							int cost=add(hold,-r)+add(hold2,-g);
							
							dp[0][g][b+1][2]=min(dp[0][g][b+1][2],dp[0][g][b][last]+cost);
						}
					}
				}
			}
		}
		
		for(int g=0;g<(int)v[1].size();g++){
			for(int b=0;b<(int)v[2].size();b++){
				for(int last=0;last<3;last++){
					dp[0][g][b][last]=dp[1][g][b][last];
					dp[1][g][b][last]=1e15;
				}
			}
		}
	}
	
	int ans=min({dp[0][v[1].size()-1][v[2].size()-1][0],dp[0][v[1].size()-1][v[2].size()-1][1],dp[0][v[1].size()-1][v[2].size()-1][2]});
	if(ans>=1e12){
		cout << -1;
	}
	else cout << ans;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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