Submission #1305309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305309		neonglitch	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	249 ms	2068 KiB

joi2019_ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=205,M=402;
int cnt[M][5];
int dp[N][N][5],ndp[N][N][5];
vector<int> oc[N];
int cost(int r,int g,int b,int wt)
{
	
	int cnt1 [] ={r,g,b};
	if(oc[wt].size()<=cnt1[wt-1])
	{
		return 1e9;
	}
	int ind=oc[wt][cnt1[wt-1]];
	return max(0,cnt[ind][1]-r)+max(0,cnt[ind][2]-g)+max(0,cnt[ind][3]-b);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='R')s[i]=char(1);
		else if(s[i]=='G')s[i]=char(2);
		else s[i]=char(3);
		
		oc[s[i]].push_back(i);
		

		
		for(int j=0;j<4;j++)cnt[i+1][j]+=cnt[i][j];
		cnt[i+1][s[i]]++;		
	}
	int lim=(n+1)/2;
	for(int c=0;c<=3;c++)
	{
		if((int)(oc[c].size())>lim)
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	for(int cr=0;cr<=lim;cr++)
	{
		for(int cg=0;cg<=lim;cg++)
		{
			for(int j=0;j<4;j++)
			{
				ndp[cr][cg][j]=1e9;
				dp[cr][cg][j]=1e9;
			}
		}
	}

	dp[0][0][0]=0;
	for(int l=0;l<n;l++)
	{
		for(int cr=0;cr<=lim;cr++)
		{
			for(int cg=0;cg<=lim and cg+cr<=l;cg++)
			{
				for(int k=1;k<=3;k++)
				{
					int p=cost(cr,cg,l-cr-cg,k);
					for(int j=0;j<4;j++)
					{
						if(j==k)continue;
						ndp[cr+(k==1)][cg+(k==2)][k] = min(ndp[cr+(k==1)][cg+(k==2)][k], dp[cr][cg][j] + p);
					}
				}
			}
		}
		for(int cr=0;cr<=lim;cr++)
		{
			for(int cg=0;cg<=lim;cg++)
			{
				for(int j=0;j<4;j++)
				{
					dp[cr][cg][j]=ndp[cr][cg][j];
					ndp[cr][cg][j]=1e9;
				}
			}
		}
	}
	int ans=1e9;
	for(int cr=0;cr<=lim;cr++)
	{
		for(int cg=0;cg<=lim;cg++)
		{
			for(int j=0;j<4;j++)
			{
				ans=min(ans,dp[cr][cg][j]);
			}
		}
	}	
	cout<<ans<<endl;
}

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