Submission #376928

#	Time	Username	Problem	Language	Result	Execution time	Memory
376928		peijar	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	1115 ms	434080 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define int long long
using namespace std;

/*
 * Quand on fait un swap : on décale quelqu'un vers la droite :
 * Donc on ramasse une plante, et on la repose plus tard 
 * Quand on voit une plante : soit on la pose direct si on peut,
 * soit on la ramasse et on la pose plus tard
 *
 * Situation : nbVues, derniere fleur posée, nbRouges, nbVertes, nbJaunes
 * O(n^4)
 */

const int MAXN = 61;

int dp[MAXN][4][MAXN][MAXN][MAXN];

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbFleurs;
	string fleurs;
	cin >> nbFleurs >> fleurs;

	for (int nbPosees(0); nbPosees < MAXN; ++nbPosees)
		for (int dernier(0); dernier < 4; ++dernier)
			for (int nbRouges(0); nbRouges < MAXN; ++nbRouges)
				for (int nbVertes(0); nbVertes < MAXN; ++nbVertes)
					for (int nbJaunes(0); nbJaunes < MAXN; ++nbJaunes)
						dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes] = 1e18;
	dp[0][0][0][0][0] = 0;
	for (int nbPosees(0); nbPosees< nbFleurs; ++nbPosees)
		for (int dernier(0); dernier < 4; ++dernier)
			for (int nbRouges(0); nbRouges <= nbFleurs; ++nbRouges)
				for (int nbVertes(0); nbVertes <= nbFleurs; ++nbVertes)
					for (int nbJaunes(0); nbJaunes <= nbFleurs; ++nbJaunes)
					{
						if (dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes] == 1e18)
							continue;
						// Soit on pose une fleur :
						int cost = dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes]
							+ nbRouges + nbVertes + nbJaunes;
						if (nbRouges and dernier != 1)
							dp[nbPosees+1][1][nbRouges-1][nbVertes][nbJaunes] 
								= min(dp[nbPosees+1][1][nbRouges-1][nbVertes][nbJaunes], cost-nbRouges);
						if (nbVertes and dernier != 2)
							dp[nbPosees+1][2][nbRouges][nbVertes-1][nbJaunes] 
								= min(dp[nbPosees+1][2][nbRouges][nbVertes-1][nbJaunes], cost-nbVertes);
						if (nbJaunes and dernier != 3)
							dp[nbPosees+1][3][nbRouges][nbVertes][nbJaunes-1] 
								= min(dp[nbPosees+1][3][nbRouges][nbVertes][nbJaunes-1], cost-nbJaunes);
						if (nbPosees + nbRouges + nbVertes + nbJaunes >= nbFleurs) continue;
						// Soit on ramasse une fleur :
						cost-= nbRouges + nbVertes + nbJaunes;
						char cur = fleurs[nbPosees+nbRouges+nbVertes+nbJaunes];
						if (cur == 'R')
							dp[nbPosees][dernier][nbRouges+1][nbVertes][nbJaunes] =
								min(dp[nbPosees][dernier][nbRouges+1][nbVertes][nbJaunes],
										cost);
						else if (cur == 'G')
							dp[nbPosees][dernier][nbRouges][nbVertes+1][nbJaunes] =
								min(dp[nbPosees][dernier][nbRouges][nbVertes+1][nbJaunes],
										cost);
						else
							dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes+1] =
								min(dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes+1],
										cost);
					}
	int rep = 1e18;
	for (int dernier(1); dernier < 4; ++dernier)
		rep = min(rep, dp[nbFleurs][dernier][0][0][0]);
	if (rep == 1e18)
		rep = -1;
	cout << rep << endl;
}

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