oj.uz

Submission #376928

# Submission time Handle Problem Language Result Execution time Memory
376928 2021-03-12T07:48:53 Z peijar Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 434080 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

/*
 * Quand on fait un swap : on décale quelqu'un vers la droite :
 * Donc on ramasse une plante, et on la repose plus tard 
 * Quand on voit une plante : soit on la pose direct si on peut,
 * soit on la ramasse et on la pose plus tard
 *
 * Situation : nbVues, derniere fleur posée, nbRouges, nbVertes, nbJaunes
 * O(n^4)
 */

const int MAXN = 61;

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

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbFleurs;
	string fleurs;
	cin >> nbFleurs >> fleurs;

	for (int nbPosees(0); nbPosees < MAXN; ++nbPosees)
		for (int dernier(0); dernier < 4; ++dernier)
			for (int nbRouges(0); nbRouges < MAXN; ++nbRouges)
				for (int nbVertes(0); nbVertes < MAXN; ++nbVertes)
					for (int nbJaunes(0); nbJaunes < MAXN; ++nbJaunes)
						dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes] = 1e18;
	dp[0][0][0][0][0] = 0;
	for (int nbPosees(0); nbPosees< nbFleurs; ++nbPosees)
		for (int dernier(0); dernier < 4; ++dernier)
			for (int nbRouges(0); nbRouges <= nbFleurs; ++nbRouges)
				for (int nbVertes(0); nbVertes <= nbFleurs; ++nbVertes)
					for (int nbJaunes(0); nbJaunes <= nbFleurs; ++nbJaunes)
					{
						if (dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes] == 1e18)
							continue;
						// Soit on pose une fleur :
						int cost = dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes]
							+ nbRouges + nbVertes + nbJaunes;
						if (nbRouges and dernier != 1)
							dp[nbPosees+1][1][nbRouges-1][nbVertes][nbJaunes] 
								= min(dp[nbPosees+1][1][nbRouges-1][nbVertes][nbJaunes], cost-nbRouges);
						if (nbVertes and dernier != 2)
							dp[nbPosees+1][2][nbRouges][nbVertes-1][nbJaunes] 
								= min(dp[nbPosees+1][2][nbRouges][nbVertes-1][nbJaunes], cost-nbVertes);
						if (nbJaunes and dernier != 3)
							dp[nbPosees+1][3][nbRouges][nbVertes][nbJaunes-1] 
								= min(dp[nbPosees+1][3][nbRouges][nbVertes][nbJaunes-1], cost-nbJaunes);
						if (nbPosees + nbRouges + nbVertes + nbJaunes >= nbFleurs) continue;
						// Soit on ramasse une fleur :
						cost-= nbRouges + nbVertes + nbJaunes;
						char cur = fleurs[nbPosees+nbRouges+nbVertes+nbJaunes];
						if (cur == 'R')
							dp[nbPosees][dernier][nbRouges+1][nbVertes][nbJaunes] =
								min(dp[nbPosees][dernier][nbRouges+1][nbVertes][nbJaunes],
										cost);
						else if (cur == 'G')
							dp[nbPosees][dernier][nbRouges][nbVertes+1][nbJaunes] =
								min(dp[nbPosees][dernier][nbRouges][nbVertes+1][nbJaunes],
										cost);
						else
							dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes+1] =
								min(dp[nbPosees][dernier][nbRouges][nbVertes][nbJaunes+1],
										cost);
					}
	int rep = 1e18;
	for (int dernier(1); dernier < 4; ++dernier)
		rep = min(rep, dp[nbFleurs][dernier][0][0][0]);
	if (rep == 1e18)
		rep = -1;
	cout << rep << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 433900 KB Output is correct
2 Correct 250 ms 433900 KB Output is correct
3 Correct 280 ms 433900 KB Output is correct
4 Correct 275 ms 433904 KB Output is correct
5 Incorrect 259 ms 433900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 433900 KB Output is correct
2 Correct 250 ms 433900 KB Output is correct
3 Correct 280 ms 433900 KB Output is correct
4 Correct 275 ms 433904 KB Output is correct
5 Incorrect 259 ms 433900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 434080 KB Output is correct
2 Execution timed out 1115 ms 433912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 433900 KB Output is correct
2 Correct 250 ms 433900 KB Output is correct
3 Correct 280 ms 433900 KB Output is correct
4 Correct 275 ms 433904 KB Output is correct
5 Incorrect 259 ms 433900 KB Output isn't correct
6 Halted 0 ms 0 KB -