Submission #826333

#	Time	Username	Problem	Language	Result	Execution time	Memory
826333		MasterTaster	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	81 ms	97244 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 410
#define MAXX 1000000010LL

using namespace std;

int n;
ll cnt1, cnt2, cnt3, cnt[5][MAXN][5];
string s;

ll koliko(int a, int i, int j, int k)
{
	if (a==1)
		return max(0LL, cnt[1][i][2]-j)+max(0LL, cnt[1][i][3]-k);
	else if (a==2)
		return max(0LL, cnt[2][j][1]-i)+max(0LL, cnt[2][j][3]-k);
	else
		return max(0LL, cnt[3][k][1]-i)+max(0LL, cnt[3][k][2]-j);
}

int main(){
	///R=1; G=2; Y=3;

	cin>>n>>s;

	for (int i=0; i<n; i++)
	{
		if (s[i]=='R') { cnt1++; }
		else if (s[i]=='G') { cnt2++; }
		else {cnt3++; }
		
		if (s[i]=='R') { cnt[1][cnt1][2]=cnt2; cnt[1][cnt1][3]=cnt3; }
		else if (s[i]=='G') { cnt[2][cnt2][1]=cnt1; cnt[2][cnt2][3]=cnt3; }
		else { cnt[3][cnt3][1]=cnt1; cnt[3][cnt3][2]=cnt2; }
	}

	/*for (int i=0; i<=cnt1; i++) cout<<cnt[1][i][2]<<" "<<cnt[1][i][3]<<endl;
	cout<<endl;
	for (int i=0; i<=cnt2; i++) cout<<cnt[2][i][1]<<" "<<cnt[2][i][3]<<endl;
	cout<<endl;
	for (int i=0; i<=cnt3; i++) cout<<cnt[3][i][1]<<" "<<cnt[3][i][2]<<endl;
	cout<<endl;*/

	ll dp[3+2][cnt1+2][cnt2+2][cnt3+2];

	for (int i=0; i<=cnt1; i++) for (int j=0; j<=cnt2; j++) for (int k=0; k<=cnt3; k++) dp[1][i][j][k]=dp[2][i][j][k]=dp[3][i][j][k]=MAXX;

	dp[1][1][0][0]=cnt[1][1][2]+cnt[1][1][3]; //cout<<dp[1][1][0][0]<<endl;
	dp[2][0][1][0]=cnt[2][1][1]+cnt[2][1][3]; //cout<<dp[2][0][1][0]<<endl;
	dp[3][0][0][1]=cnt[3][1][1]+cnt[3][1][2]; //cout<<dp[3][0][0][1]<<endl;
	//cout<<endl;

	for (int sum=2; sum<=n; sum++)
	{
		for (int i=0; i<=min((ll)sum, cnt1); i++)
		{
			for (int j=0; j<=min(cnt2, (ll)(sum-i)); j++)
			{
				int k=sum-i-j;
				if (k>cnt3) continue;

				if (i==0) dp[1][i][j][k]=MAXX;
				else dp[1][i][j][k]=min(dp[2][i-1][j][k]+koliko(1, i, j, k), dp[3][i-1][j][k]+koliko(1, i, j, k));

				if (j==0) dp[2][i][j][k]=MAXX;
				else dp[2][i][j][k]=min(dp[1][i][j-1][k]+koliko(2, i, j, k), dp[3][i][j-1][k]+koliko(2, i, j, k));

				if (k==0) dp[3][i][j][k]=MAXX;
				else dp[3][i][j][k]=min(dp[1][i][j][k-1]+koliko(3, i, j, k), dp[2][i][j][k-1]+koliko(3, i, j, k));

				//cout<<i<<" "<<j<<" "<<k<<":"<<endl;
				//cout<<dp[1][i][j][k]<<" "<<dp[2][i][j][k]<<" "<<dp[3][i][j][k]<<endl;
			}
		}
	}

	ll ress=min(dp[1][cnt1][cnt2][cnt3], min(dp[2][cnt1][cnt2][cnt3], dp[3][cnt1][cnt2][cnt3]));
	if (ress>=MAXX) cout<<-1;
	else cout<<ress;

	return 0;
}

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