Submission #376976

#	Time	Username	Problem	Language	Result	Execution time	Memory
376976		peijar	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	622 ms	1009772 KiB

joi2019_ho_t3

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

const int MAXN = 401;
const int INF = 1e9;

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

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbFleurs;
	string fleurs;
	cin >> nbFleurs >> fleurs;
	vector<vector<int>> positions(3);
	vector<vector<int>> prefixSum(3, vector<int>(nbFleurs+1));
	for (int i(0); i < nbFleurs; ++i)
	{
		for (int j(0); j < 3; ++j)
			prefixSum[j][i+1] = prefixSum[j][i];
		if (fleurs[i] == 'R')
		{
			positions[0].push_back(i);
			prefixSum[0][i+1]++;
		}
		else if (fleurs[i] == 'G')
		{
			positions[1].push_back(i);
			prefixSum[1][i+1]++;
	}
		else
		{
			positions[2].push_back(i);
			prefixSum[2][i+1]++;
		}
	}
	for (int nbRouge(0); nbRouge <= nbFleurs; ++nbRouge)
		for (int nbVerts(0); nbVerts <= nbFleurs; ++nbVerts)
			for (int nbJaunes(0); nbJaunes <= nbFleurs; ++nbJaunes)
				for (int dernier(0); dernier < 4; ++dernier)
					dp[nbRouge][nbVerts][nbJaunes][dernier]= INF;
	int rep = INF;
	int totRouges = (int)positions[0].size();
	int totVerts = (int)positions[1].size();
	int totJaunes = (int)positions[2].size();
	assert(totRouges >= 0 and totVerts >= 0 and totJaunes >= 0);
	dp[0][0][0][3] = 0;
	for (int nbRouge(0); nbRouge <= totRouges; ++nbRouge)
		for (int nbVerts(0); nbVerts <= totVerts; ++nbVerts)
			for (int nbJaunes(0); nbJaunes <= totJaunes ; ++nbJaunes)
				for (int dernier(0); dernier < 4; ++dernier)
				{
					int prix = dp[nbRouge][nbVerts][nbJaunes][dernier];
					if (prix == INF) continue;
					int curPos[3] = {nbRouge, nbVerts, nbJaunes};
					for (int prochain(0); prochain < 3; ++prochain)
					{
						if (curPos[prochain] >= (int)positions[prochain].size())
							continue;
						if (prochain == dernier) continue;
						int nbSwap(0);
						for (int autres(0); autres < 3; ++autres)
							if (autres != prochain and curPos[autres] < (int)positions[autres].size())
							{
								int posNxt = positions[prochain][curPos[prochain]];
								int posAutres = positions[autres][curPos[autres]];
								if (posNxt > posAutres)
									nbSwap += prefixSum[autres][posNxt+1] - prefixSum[autres][posAutres];
							}
						int nxtRouges = nbRouge, nxtVerts = nbVerts, nxtJaunes = nbJaunes;
						if (!prochain) nxtRouges++;
						else if (prochain == 1) nxtVerts++;
						else nxtJaunes++;
						dp[nxtRouges][nxtVerts][nxtJaunes][prochain] = 
						min(dp[nxtRouges][nxtVerts][nxtJaunes][prochain], nbSwap + prix);
					}
				}
	for (int dernier(0); dernier < 3; ++dernier)
		rep = min(rep, dp[totRouges][totVerts][totJaunes][dernier]);

	if (rep == INF)
		rep = -1;
	cout << rep << endl;
}

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