oj.uz

Submission #376984

# Submission time Handle Problem Language Result Execution time Memory
376984 2021-03-12T14:38:11 Z peijar Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
20 / 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[2][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
5.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 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 1516 KB Output is correct
8 Correct 1 ms 1516 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 1 ms 1536 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 1 ms 1516 KB Output is correct
13 Correct 1 ms 1516 KB Output is correct
14 Correct 1 ms 1388 KB Output is correct
15 Correct 1 ms 1516 KB Output is correct
16 Correct 1 ms 1516 KB Output is correct
17 Correct 1 ms 1388 KB Output is correct

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 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 1516 KB Output is correct
8 Correct 1 ms 1516 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 1 ms 1536 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 1 ms 1516 KB Output is correct
13 Correct 1 ms 1516 KB Output is correct
14 Correct 1 ms 1388 KB Output is correct
15 Correct 1 ms 1516 KB Output is correct
16 Correct 1 ms 1516 KB Output is correct
17 Correct 1 ms 1388 KB Output is correct
18 Incorrect 10 ms 18028 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 499 ms 757612 KB Output is correct
3 Correct 492 ms 755436 KB Output is correct
4 Correct 478 ms 757484 KB Output is correct
5 Correct 491 ms 757612 KB Output is correct
6 Correct 482 ms 757484 KB Output is correct
7 Correct 469 ms 755308 KB Output is correct
8 Correct 477 ms 755308 KB Output is correct
9 Correct 475 ms 751724 KB Output is correct
10 Correct 500 ms 757484 KB Output is correct
11 Correct 484 ms 757484 KB Output is correct
12 Correct 117 ms 202860 KB Output is correct
13 Correct 216 ms 357484 KB Output is correct
14 Correct 320 ms 517484 KB Output is correct
15 Correct 477 ms 757484 KB Output is correct
16 Correct 475 ms 757484 KB Output is correct

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 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1516 KB Output is correct
7 Correct 1 ms 1516 KB Output is correct
8 Correct 1 ms 1516 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 1 ms 1536 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 1 ms 1516 KB Output is correct
13 Correct 1 ms 1516 KB Output is correct
14 Correct 1 ms 1388 KB Output is correct
15 Correct 1 ms 1516 KB Output is correct
16 Correct 1 ms 1516 KB Output is correct
17 Correct 1 ms 1388 KB Output is correct
18 Incorrect 10 ms 18028 KB Output isn't correct
19 Halted 0 ms 0 KB -