Submission #254175

#	Time	Username	Problem	Language	Result	Execution time	Memory
254175		cobra_	Miners (IOI07_miners)	C++14	100 / 100	262 ms	100984 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8