Submission #157558

#TimeUsernameProblemLanguageResultExecution timeMemory
157558faremyMiners (IOI07_miners)C++14
100 / 100
157 ms100676 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...