Submission #960273

#	Time	Username	Problem	Language	Result	Execution time	Memory
960273		LCJLY	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	75 ms	8436 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;
	dp[0][0][0][1]=0;
	dp[0][0][0][2]=0;
	
	int ans=1e15;
	
	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){
						if(r<(int)v[0].size())dp[1][g][b][0]=min(dp[1][g][b][0],dp[0][g][b][last]+v[0][r]);
						
						if(g<(int)v[1].size())dp[0][g+1][b][1]=min(dp[0][g+1][b][1],dp[0][g][b][last]+v[1][g]);
						
						if(g<(int)v[2].size())dp[0][g][b+1][2]=min(dp[0][g][b+1][2],dp[0][g][b][last]+v[2][b]);
					}	
					else{
						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);
							
							dp[1][g][b][0]=min(dp[1][g][b][0],dp[0][g][b][last]+cost);
						}
						
						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);
							
							dp[0][g+1][b][1]=min(dp[0][g+1][b][1],dp[0][g][b][last]+cost);
						}
						
						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);
							
							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++){
					//show(r,r);
					//show3(g,g,b,b,last,last);
					//show(dp[1][g][b][last],dp[1][g][b][last]);
					if(r+g+b==n){
						ans=min(ans,dp[0][g][b][last]);
					}
					dp[0][g][b][last]=dp[1][g][b][last];
					dp[1][g][b][last]=1e15;
				}
			}
		}
	}

	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: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25