Submission #1329314

#TimeUsernameProblemLanguageResultExecution timeMemory
1329314paronmanukyanMiners (IOI07_miners)C++20
100 / 100
425 ms101112 KiB
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 2e5 + 10;
const ll inf = 1e18;

int dp[M][4][4][4][4];
int a[M];

void solve()
{
	int n;
	cin >> n;

	string s;
	cin >> s;
	//cout << s << endl;
	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'M')
			a[i + 1] = 1;
		else if (s[i] == 'F')
			a[i + 1] = 2;
		else if (s[i] == 'B')
			a[i + 1] = 3;
	}
	//for (int i = 1; i <= n; ++i)
	//	cout << a[i] << " ";
	dp[1][0][a[1]][0][0] = 1;
	dp[1][0][0][0][a[1]] = 1;
	function<int(int, int, int)> ans = [](int x, int y, int z) -> int {
		set<int> s;
		s.insert(x), s.insert(y), s.insert(z);
		s.erase(0);
		return s.size();
		};
	for (int i = 1; i < n; i++)
	{
		for (int last1 = 0; last1 <= 3; last1++)
		{
			for (int last2 = 0; last2 <= 3; last2++)
			{
				for (int last3 = 0; last3 <= 3; ++last3) 
				{
					for (int last4 = 0; last4 <= 3; ++last4)
					{
						if (dp[i][last1][last2][last3][last4] == 0)
							continue;
						dp[i + 1][last1][last2][last4][a[i + 1]] = max(
							dp[i + 1][last1][last2][last4][a[i + 1]],
							dp[i][last1][last2][last3][last4] +
							ans(last3, last4, a[i + 1]));
						dp[i + 1][last2][a[i + 1]][last3][last4] = max(
							dp[i + 1][last2][a[i + 1]][last3][last4],
							dp[i][last1][last2][last3][last4] +
							ans(last1, last2, a[i + 1]));
					}
				}
			}
		}
	}
	int answer = 0;
	for (int last1 = 0; last1 <= 3; last1++)
	{
		for (int last2 = 0; last2 <= 3; last2++)
		{
			for (int last3 = 0; last3 <= 3; ++last3)
			{
				for (int last4 = 0; last4 <= 3; ++last4)
				{
					answer = max(answer, 
						dp[n][last1][last2][last3][last4]);
				}
			}
		}
	}
	cout << answer << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	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...