Submission #533699

#	Time	Username	Problem	Language	Result	Execution time	Memory
533699		alvingogo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	185 ms	134800 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
#define vi vector<int>
#define vvi vector<vi> 
#define vvvi vector<vvi>
#define vvvvi vector<vvvi> 
using namespace std;

const int inf=1e9+7;
int main(){
	AquA;
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cr=0,cb=0,cg=0;
	vi rr,bb,gg,tg(n+1),tb(n+1),tr(n+1);
	rr.push_back(-1);
	bb.push_back(-1);
	gg.push_back(-1);
	for(int i=0;i<n;i++){
		tr[i]=tr[(i-1)*(i>0)];
		tb[i]=tb[(i-1)*(i>0)];
		tg[i]=tg[(i-1)*(i>0)];
		if(s[i]=='R'){
			tr[i]++;
			cr++;
			rr.push_back(i);
		}
		else if(s[i]=='Y'){
			tb[i]++;
			cb++;
			bb.push_back(i);
		}
		else{
			tg[i]++;
			cg++;
			gg.push_back(i);
		}
	}
	vvvvi dp(cr+1,vvvi(cb+1,vvi(cg+1,vi(3,inf))));
	dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
	for(int r=0;r<=cr;r++){
		for(int b=0;b<=cb;b++){
			for(int g=0;g<=cg;g++){
				if(r>0){
					int c=max(0,tg[rr[r]]-g)+max(0,tb[rr[r]]-b);
					dp[r][b][g][0]=min(dp[r][b][g][0],min(dp[r-1][b][g][1],dp[r-1][b][g][2])+c);
				}
				if(b>0){
					int c=max(0,tg[bb[b]]-g)+max(0,tr[bb[b]]-r);
					dp[r][b][g][1]=min(dp[r][b][g][1],min(dp[r][b-1][g][0],dp[r][b-1][g][2])+c);
				}
				if(g>0){
					int c=max(0,tb[gg[g]]-b)+max(0,tr[gg[g]]-r);
					dp[r][b][g][2]=min(dp[r][b][g][2],min(dp[r][b][g-1][0],dp[r][b][g-1][1])+c);
				}
				//cout << r << " " << b << " " << g << " " << dp[r][b][g][0] << " " << dp[r][b][g][1] << " " << dp[r][b][g][2] << "\n";
			}
		}
	}
	int h=min(dp[cr][cb][cg][0],min(dp[cr][cb][cg][1],dp[cr][cb][cg][2]));
	if(h==inf){
		cout << -1 << "\n";
	}
	else{
		cout << h << "\n";
	}
	return 0;
}

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