제출 #1305308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305308		neonglitch	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	611 ms	99864 KiB

joi2019_ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=205;
int dp[N][N][5],ndp[N][N][5];
vector<int> oc[N];
int memo[N][N][N][3];
int cost(int r,int g,int b,int wt)
{
	
	int cnt [] ={r,g,b};
	if(oc[wt].size()<=cnt[wt-1])
	{
		return 1e9;
	}
	return memo[r][g][b][wt-1];
}
int cost1(int r,int g,int b,int wt)
{
	int cnt [] ={r,g,b};
	if(oc[wt].size()<=cnt[wt-1])
	{
		return 1e9;
	}
	int ind=oc[wt][cnt[wt-1]];
	int ls = lower_bound(begin(oc[1])+r,end(oc[1]),ind)-(begin(oc[1])+r);
	ls += lower_bound(begin(oc[2])+g,end(oc[2]),ind)-(begin(oc[2])+g);
	ls += lower_bound(begin(oc[3])+b,end(oc[3]),ind)-(begin(oc[3])+b);
	return ls;
}
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);
	}
	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 cg=0;cg<=lim;cg++)
	{
		for(int cr=0;cr<=lim and cr+cg<=n;cr++)
		{
			for(int c=0;c<=lim and c+cr+cg<=n;c++)
			{
				for(int k=1;k<=3;k++)
					memo[cr][cg][c][k-1]=cost1(cr,cg,c,k);
			}
		}
	}
	// len
	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: 0 / 15
• Subtask 4: 0 / 25