oj.uz

Submission #254175

# Submission time Handle Problem Language Result Execution time Memory
254175 2020-07-29T12:53:12 Z cobra_ Miners (IOI07_miners) C++14
100 / 100
 262 ms 100984 KB 
#include <iostream>
#include <vector>
#include <algorithm>

const int MAX_MINERS = 1e5;
const int NB_VALUES = 4;
const int INF = 1e8;

int dp[MAX_MINERS + 1][NB_VALUES][NB_VALUES][NB_VALUES][NB_VALUES];

int get_score(int type1, int type2, int type3)
{
	if (type2 == 0)
		return 1;
	if (type1 == 0)
		return 1 + (type2 != type3);

	if (type1 == type2 && type2 == type3)
		return 1;
	if (type1 != type2 && type1 != type3 && type2 != type3)
		return 3;
	return 2;
}

void update(int& old, int val)
{
	if (val > old)
		old = val;
}

int main()
{
	int nbShipments;
	std::cin >> nbShipments;

	std::vector<int> shipments(nbShipments);
	for (int& shipment: shipments)
	{
		char c;
		std::cin >> c;

		switch(c)
		{
			case 'M': shipment = 1; break;
			case 'F': shipment = 2; break;
			case 'B': shipment = 3; break;
		}
	}

	std::fill_n((int*)(dp), MAX_MINERS * NB_VALUES * NB_VALUES * NB_VALUES * NB_VALUES, -INF);
	dp[0][0][0][0][0] = 0;

	for (int iShipment = 0; iShipment < nbShipments; iShipment++)
		for (int typeA1 = 0; typeA1 < NB_VALUES; typeA1++)
			for (int typeA2 = 0; typeA2 < NB_VALUES; typeA2++)
				for (int typeB1 = 0; typeB1 < NB_VALUES; typeB1++)
					for (int typeB2 = 0; typeB2 < NB_VALUES; typeB2++)
					{
						update(dp[iShipment+1][typeA2][shipments[iShipment]][typeB1][typeB2], dp[iShipment][typeA1][typeA2][typeB1][typeB2] + get_score(typeA1, typeA2, shipments[iShipment]));
						update(dp[iShipment+1][typeA1][typeA2][typeB2][shipments[iShipment]], dp[iShipment][typeA1][typeA2][typeB1][typeB2] + get_score(typeB1, typeB2, shipments[iShipment]));
					}

	int maxFound = 0;
	for (int typeA1 = 0; typeA1 < NB_VALUES; typeA1++)
		for (int typeA2 = 0; typeA2 < NB_VALUES; typeA2++)
			for (int typeB1 = 0; typeB1 < NB_VALUES; typeB1++)
				for (int typeB2 = 0; typeB2 < NB_VALUES; typeB2++)
					maxFound = std::max(maxFound, dp[nbShipments][typeA1][typeA2][typeB1][typeB2]);

	std::cout << maxFound << '\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 100472 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 100472 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 100600 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 100472 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 100604 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 100472 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 100452 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 100480 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 100600 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 100732 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 100860 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 100984 KB Output is correct