Submission #157558

#	Time	Username	Problem	Language	Result	Execution time	Memory
157558		faremy	Miners (IOI07_miners)	C++14	100 / 100	157 ms	100676 KiB

miners

#include <iostream>
#include <algorithm>


const int MAXN = 1e5 + 1;
const int NOPE = -1e9;

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


int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int shipments; std::cin >> shipments;
	std::fill_n((int *)dp, (shipments + 1) * 256, NOPE);
	dp[0][0][0][0][0] = 0;

	for (int iShipment = 0; iShipment < shipments; iShipment++)
	{
		char t; std::cin >> t;
		int type = 0;

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

		for (int a = 0; a < 4; a++)
			for (int b = 0; b < 4; b++)
			{
				int nxt1 = 0;
				if (a == 0 && b == 0)
					nxt1 = 1;
				else if (a == 0)
					nxt1 = 2 - (b == type);
				else
					nxt1 = 3 - std::min(2, (a == b) + (b == type) + (a == type));

				for (int c = 0; c < 4; c++)
					for (int d = 0; d < 4; d++)
					{
						if (dp[iShipment][a][b][c][d] == NOPE)
							continue;

						int nxt2 = 0;
						if (c == 0 && d == 0)
							nxt2 = 1;
						else if (c == 0)
							nxt2 = 2 - (d == type);
						else
							nxt2 = 3 - std::min(2, (c == d) + (d == type) + (c == type));

						dp[iShipment + 1][b][type][c][d] = std::max(dp[iShipment + 1][b][type][c][d], dp[iShipment][a][b][c][d] + nxt1);
						dp[iShipment + 1][a][b][d][type] = std::max(dp[iShipment + 1][a][b][d][type], dp[iShipment][a][b][c][d] + nxt2);
					}
			}
	}

	int ans = 0;
	for (int a = 0; a < 4; a++)
		for (int b = 0; b < 4; b++)
			for (int c = 0; c < 4; c++)
				for (int d = 0; d < 4; d++)
					ans = std::max(ans, dp[shipments][a][b][c][d]);
	
	std::cout << ans << '\n';

	return 0;
}

• 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