oj.uz

Submission #376983

# Submission time Handle Problem Language Result Execution time Memory
376983 2021-03-12T14:31:57 Z peijar Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 757612 KB 
#include <bits/stdc++.h>
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();
	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 nbRouge(0); nbRouge <= totRouges; ++nbRouge)
		for (int nbVerts(0); nbVerts <= totVerts; ++nbVerts)
			for (int nbJaunes(0); nbJaunes <= totJaunes ; ++nbJaunes)
				for (int dernier(0); dernier < 3; ++dernier)
					if (dp[nbRouge][nbVerts][nbJaunes][dernier] < INF)
					{
						int prix = dp[nbRouge][nbVerts][nbJaunes][dernier];
						// On met un rouge : 
						if (nbRouge < totRouges and dernier)
						{
							int nbSwaps = 0;
							if (nbVerts < totVerts and positions[0][nbRouge] > positions[1][nbVerts])
								nbSwaps += prefixSum[1][positions[0][nbRouge]]
									 - prefixSum[1][positions[1][nbVerts]];
							if (nbJaunes < totJaunes and positions[0][nbRouge] > positions[2][nbJaunes])
								nbSwaps += prefixSum[2][positions[0][nbRouge]]
									- prefixSum[2][positions[1][nbJaunes]];
							dp[nbRouge+1][nbVerts][nbJaunes][0]
								= min(dp[nbRouge+1][nbVerts][nbJaunes][0], prix+nbSwaps);
						}
						// On met un vert :
						if (nbVerts < totVerts and dernier != 1)
						{
							int nbSwaps = 0;
							if (nbRouge < totRouges and positions[1][nbVerts] > positions[0][nbRouge])
								nbSwaps += prefixSum[0][positions[1][nbVerts]]
									 - prefixSum[0][positions[0][nbRouge]];
							if (nbJaunes < totJaunes and positions[1][nbVerts] > positions[2][nbJaunes])
								nbSwaps += prefixSum[2][positions[1][nbVerts]]
									- prefixSum[2][positions[2][nbJaunes]];
							dp[nbRouge][nbVerts+1][nbJaunes][1]
								= min(dp[nbRouge][nbVerts+1][nbJaunes][1], prix+nbSwaps);
						}
						if (nbJaunes < totJaunes and dernier != 2)
						{
							int nbSwaps = 0;
							if (nbRouge < totRouges and positions[2][nbJaunes] > positions[0][nbRouge])
								nbSwaps += prefixSum[0][positions[2][nbJaunes]]
									 - prefixSum[0][positions[0][nbRouge]];
							if (nbVerts < totVerts and positions[2][nbJaunes] > positions[1][nbJaunes])
								nbSwaps += prefixSum[1][positions[2][nbJaunes]]
									- prefixSum[1][positions[1][nbVerts]];
							dp[nbRouge][nbVerts][nbJaunes+1][2]
								= min(dp[nbRouge][nbVerts][nbJaunes+1][2], prix+nbSwaps);
						}
					}
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 476 ms 757484 KB Output is correct
3 Correct 476 ms 755272 KB Output is correct
4 Correct 479 ms 757568 KB Output is correct
5 Correct 480 ms 757464 KB Output is correct
6 Correct 479 ms 757484 KB Output is correct
7 Correct 486 ms 755308 KB Output is correct
8 Correct 480 ms 755308 KB Output is correct
9 Correct 471 ms 751724 KB Output is correct
10 Execution timed out 507 ms 757612 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 876 KB Output isn't correct
5 Halted 0 ms 0 KB -