Submission #1282545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282545		WH8	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	143 ms	58592 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double

void chmin(int & x, int v){
	x=min(x, v);
}	

signed main(){
	int n;cin>>n;
	vector<int> v(n+1);
	vector<vector<int>> pos(3);
	for(int i=0;i<3;i++)pos[i].pb(0);
	vector<vector<int>> ps(3, vector<int>(n+1, 0));
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='R')v[i]=0;
		else if(c=='Y')v[i]=1;
		else v[i]=2;
		for(int j=0;j<3;j++)ps[j][i]=ps[j][i-1];
		ps[v[i]][i]++;
		pos[v[i]].pb(i);
	}
	//~ for(int i=0;i<3;i++){
		//~ printf("size of pos %lld is %lld\n", i, pos[i].size());
		//~ for(auto it:pos[i])cout<<it<<" ";
		//~ cout<<endl;
	//~ }
	
	int dp[pos[0].size()+1][pos[1].size()+1][pos[2].size()+1][3];
	for(int i=0;i<=(int)pos[0].size();i++)
		for(int j=0;j<=(int)pos[1].size();j++)
			for(int k=0;k<=(int)pos[2].size();k++)
				for(int z=0;z<3;z++)
					dp[i][j][k][z]=1e9;
	dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
	array<int, 3> p={0,0,0};
	for(p[0]=0;p[0]<(int)pos[0].size();p[0]++){
		for(p[1]=0;p[1]<(int)pos[1].size();p[1]++){
			for(p[2]=0;p[2]<(int)pos[2].size();p[2]++){
				for(int z=0;z<3;z++){
					//~ printf("%lld %lld %lld %lld\n",p[0],p[1],p[2],z);
					for(int cnt=1;cnt<=2;cnt++){
						int curval=dp[p[0]][p[1]][p[2]][z];
						int to=(z+cnt)%3, a=(to+1)%3,b=(to+2)%3;
						if(p[to]==(int)pos[to].size()-1)continue;
						
						p[to]++;
						int d=max(0ll, ps[a][pos[to][p[to]]]-p[a])
							+ max(0ll, ps[b][pos[to][p[to]]]-p[b]);
						chmin(dp[p[0]][p[1]][p[2]][to],curval+d);
						//~ printf("upd %lld %lld %lld %lld with value %lld\n", p[0],p[1],p[2],to,curval+d);
						p[to]--;
					}
				}
			}
		}
	}
	int ans=1e9;
	for(int i=0;i<3;i++)ans=min(ans,
		dp[pos[0].size()-1][pos[1].size()-1][pos[2].size()-1][i]);
	if(ans >= 1e9)cout<<-1;
	else cout<<ans;
	
}

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