Submission #376990

#	Time	Username	Problem	Language	Result	Execution time	Memory
376990		peijar	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	481 ms	757740 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;

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

int dp[MAXN][MAXN][MAXN][3];

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)
	{
		if (fleurs[i] == 'R')
			positions[0].push_back(i);
		else if (fleurs[i] == 'G')
			positions[1].push_back(i);
		else
			positions[2].push_back(i);
		for (int j(0); j < 3; ++j)
			prefixSum[j][i+1] = (int)positions[j].size();
	}
	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 < 3; ++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();
	for (int i(0); i < 3; ++i)
		positions[i].push_back(nbFleurs);
	if (totRouges)
		dp[1][0][0][0] = positions[0][0];
	if (totVerts)
		dp[0][1][0][1] = positions[1][0];
	if (totJaunes)
		dp[0][0][1][2] = positions[2][0];
	for (int nbRouges(0); nbRouges <= totRouges; ++nbRouges)
		for (int nbVerts(0); nbVerts <= totVerts; ++nbVerts)
			for (int nbJaunes(0); nbJaunes <= totJaunes ; ++nbJaunes)
			{
				auto &x = dp[nbRouges][nbVerts][nbJaunes];
				int swapRouge(0), swapVerts(0), swapJaunes(0);
				int posRouge = positions[0][nbRouges];
				int posVert = positions[1][nbVerts];
				int posJaune = positions[2][nbJaunes];
				int prevPosRouge=0;
				int prevPosVert=0;
				int prevPosJaune=0;
				if (nbRouges)
				{
					prevPosRouge=positions[0][nbRouges-1];
					if (prevPosRouge > posVert)
						swapRouge += prefixSum[1][prevPosRouge] - prefixSum[1][posVert];
					if (prevPosRouge > posJaune)
						swapRouge += prefixSum[2][prevPosRouge] - prefixSum[2][posJaune];
					int bst = min(dp[nbRouges-1][nbVerts][nbJaunes][1],
							dp[nbRouges-1][nbVerts][nbJaunes][2]);
					if (bst < INF)
						x[0] = bst + swapRouge;
				}
				if (nbVerts)
				{
					prevPosVert = positions[1][nbVerts-1];
					if (prevPosVert > posRouge)
						swapVerts += prefixSum[0][prevPosVert] - prefixSum[0][posRouge];
					if (prevPosVert> posJaune)
						swapVerts += prefixSum[2][prevPosVert] - prefixSum[2][posJaune];
					int bst = min(dp[nbRouges][nbVerts-1][nbJaunes][0],
							dp[nbRouges][nbVerts-1][nbJaunes][2]);
					if (bst < INF)
						x[1] = bst + swapVerts;
				}
				if (nbJaunes)
				{
					prevPosJaune = positions[2][nbJaunes-1];
					if (prevPosJaune > posRouge)
						swapJaunes += prefixSum[0][prevPosJaune] - prefixSum[0][posRouge];
					if (prevPosJaune > posVert)
						swapJaunes += prefixSum[1][prevPosJaune] - prefixSum[1][posVert];
					int bst = min(dp[nbRouges][nbVerts][nbJaunes-1][0],
							dp[nbRouges][nbVerts][nbJaunes-1][1]);
					if (bst < INF)
						x[2] = bst + swapJaunes;
				}
			}
	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: 15 / 15
• Subtask 4: 25 / 25