oj.uz

답안 #376985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376985 2021-03-12T14:40:20 Z peijar Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
20 / 100
 427 ms 757612 KB 
#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();
	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

# 결과 실행 시간 메모리 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 876 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 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 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

# 결과 실행 시간 메모리 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 876 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 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 412 ms 757552 KB Output is correct
3 Correct 421 ms 755308 KB Output is correct
4 Correct 407 ms 757484 KB Output is correct
5 Correct 408 ms 757612 KB Output is correct
6 Correct 410 ms 757484 KB Output is correct
7 Correct 416 ms 755308 KB Output is correct
8 Correct 427 ms 755308 KB Output is correct
9 Correct 415 ms 751596 KB Output is correct
10 Correct 413 ms 757484 KB Output is correct
11 Correct 413 ms 757484 KB Output is correct
12 Correct 121 ms 202860 KB Output is correct
13 Correct 195 ms 357484 KB Output is correct
14 Correct 278 ms 517612 KB Output is correct
15 Correct 405 ms 757484 KB Output is correct
16 Correct 410 ms 757484 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 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 876 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 1 ms 1516 KB Output is correct
10 Correct 1 ms 1516 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 -