oj.uz

Submission #157558

# Submission time Handle Problem Language Result Execution time Memory
157558 2019-10-12T12:26:31 Z faremy Miners (IOI07_miners) C++14
100 / 100
 157 ms 100676 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1400 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5412 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10332 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 25416 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 75608 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 100676 KB Output is correct