Submission #755209

#	Time	Username	Problem	Language	Result	Execution time	Memory
755209		amirhoseinfar1385	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	427 ms	4180 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
const int maxn=405;
int inf=5e6;
int dp1[maxn][maxn][3],dp0[maxn][maxn][3];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	string s;
	cin>>n>>s;
	vector<int>w1,w2,w0;
	vector<int>ted0(n),ted1(n),ted2(n);
	for(int i=0;i<n;i++){
		if(i!=0){
			ted1[i]=ted1[i-1];
			ted0[i]=ted0[i-1];
			ted2[i]=ted2[i-1];
		}
		if(s[i]=='Y'){
			ted0[i]++;
			w0.push_back(i);
			continue;
		}
		if(s[i]=='G'){
			ted1[i]++;
			w1.push_back(i);
			continue;
		}
		ted2[i]++;
		w2.push_back(i);
	}
	for(int ind=0;ind<n;ind++){
		for(int i=0;i<maxn;i++){
			for(int j=0;j<maxn;j++){
				for(int h=0;h<3;h++){
					dp0[i][j][h]=dp1[i][j][h];
				}
			}
		}
		for(int i=0;i<maxn;i++){
			for(int j=0;j<maxn;j++){
				for(int h=0;h<3;h++){
					int z=ind+1-i-j;
					if(i+j>ind+1||(h==2&&i+j==ind+1)){
						dp1[i][j][h]=inf;
						continue;
					}
					if(h==0){
						if(i<=0||i>(int)w0.size()){
							dp1[i][j][h]=inf;
							continue;
						}
						dp1[i][j][h]=min(dp0[i-1][j][1],dp0[i-1][j][2])+max(ted1[w0[i-1]]-j,0)+max(ted2[w0[i-1]]-z,0);
					}
					if(h==1){
						if(j<=0||j>(int)w1.size()){
							dp1[i][j][h]=inf;
							continue;
						}
						dp1[i][j][h]=min(dp0[i][j-1][0],dp0[i][j-1][2])+max(ted0[w1[j-1]]-i,0)+max(ted2[w1[j-1]]-z,0);
						//cout<<"ted: "<<ted[w1[j-1]]<<"\n";
					}
					if(h==2){
						if(z<=0||z>(int)w2.size()){
							dp1[i][j][h]=inf;
							continue;
						}
						dp1[i][j][h]=min(dp0[i][j][0],dp0[i][j][1])+max(ted1[w2[z-1]]-j,0)+max(ted0[w2[z-1]]-i,0);
					}
			//		cout<<ind<<" "<<i<<" "<<j<<" "<<h<<" "<<dp1[i][j][h]<<"\n";
				}
			}
		}
	}
	int res=min(dp1[(int)w0.size()][(int)w1.size()][1],min(dp1[(int)w0.size()][(int)w1.size()][0],dp1[(int)w0.size()][(int)w1.size()][2]));
	//cout<<dp1[(int)w0.size()][(int)w1.size()][0]<<" "<<dp1[(int)w0.size()][(int)w1.size()][1]<<" "<<dp1[(int)w0.size()][(int)w1.size()][2]<<"\n";
	//cout<<dp0[(int)w0.size()][(int)w1.size()-1][0]<<" "<<dp0[(int)w0.size()][(int)w1.size()-1][2]<<"\n";
	if(res>=inf){
		cout<<-1<<"\n";
	}
	else{
		cout<<res<<"\n";
	}
}

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