Submission #1329086

#TimeUsernameProblemLanguageResultExecution timeMemory
1329086vache_kocharyanMiners (IOI07_miners)C++20
100 / 100
433 ms101072 KiB
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

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

#define ss second
#define ff first
#define all(X) X.begin(), X.end()
#define rall(X) X.rbegin(), X.rend()
#define cinall(X) for (auto &i : (X)) cin >> i
#define printall(X) for (auto &i : (X)) cout << i << " "
#define printFromTo(cont, i, j, ch) for (int _ = i; _ <= j; _++) cout << cont[_] << ch
#define cinFromTo(cont, i, j) for (int _ = i; _ <= j; _++) cin >> cont[_]
#define fillFromTo(cont, i, j, x) for (int _ = i; _ <= j; _++) cont[_] = x;
#define pb push_back
#define sz(X) (X).size()
#define m_p make_pair
#define pii pair<int, int>

#define MAKE_UNIQUE_KEEP_ORDER(vec) do { unordered_set<decltype((vec).front())> seen; (vec).erase(remove_if((vec).begin(), (vec).end(), [&](auto &val) { if (seen.count(val)) return true; seen.insert(val); return false; }), (vec).end()); } while(0)

#define UNIQUE_SORT(vec) do { sort((vec).begin(), (vec).end()); (vec).erase(unique((vec).begin(), (vec).end()), (vec).end()); } while(0)

#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

#define yes cout << "YES\n"
#define no cout << "NO\n"
#define YN(b) if(b) {yes;} else {no;}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) (lower_bound((c).begin(), (c).end(), (x)) - (c).begin())
#define UB(c, x) (upper_bound((c).begin(), (c).end(), (x)) - (c).begin())

const int N = 2.4e6 + 5;
const int LOG = 21;
const long long INFLL = 1e18;
const int INF = 5e8;
const long double epsilon = 0.000001;
const long long mod = 1e9 + 7;

int dx[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
int dy[] = { 0, 0, 1, -1, 1, 1, -1, -1 };

int bx[] = { 2, 2, 1, 1, -1, -1, -2, -2 };
int by[] = { 1, -1, 2, -2, 2, -2, -1, 1 };

constexpr ll TEN[] = { 1LL,10LL,100LL,1000LL,10000LL,100000LL,1000000LL,10000000LL,100000000LL,1000000000LL,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL,1000000000000000000LL, };

inline long long binPowByMod(long long x, long long power, long long modx) {
	long long res = 1;
	long long base = x % modx;
	while (power > 0) {
		if (power & 1) res = (res * base) % modx;
		base = (base * base) % modx;
		power >>= 1;
	}
	return res;
}

inline ll add(ll a, ll b, ll modx) {
	a %= modx; b %= modx;
	a += b;
	if (a >= modx) a -= modx;
	return a;
}

inline ll sub(ll a, ll b, ll modx) {
	a %= modx; b %= modx;
	a -= b;
	if (a < 0) a += modx;
	return a;
}

inline ll mult(ll a, ll b, ll modx) {
	a %= modx; b %= modx;
	return (a * b) % modx;
}

ll fact[N];
inline long long divid(long long p, long long q, long long modx) { return mult(p % modx, binPowByMod(q, modx - 2, modx), modx); }
inline ll cnk(ll a, ll b)
{
	ll ans = 1;
	ans = fact[a];
	ans = divid(ans, fact[b], mod);
	ans = divid(ans, fact[a - b], mod);
	return ans;
}


ll gcdll(ll a, ll b) { return b == 0 ? a : gcdll(b, a % b); }
ll lcmll(ll a, ll b) { return a / gcdll(a, b) * b; }
ll ceil_div(ll a, ll b) { return (a + b - 1) / b; }
bool isPrime(ll x) { if (x < 2) return false; for (ll i = 2; i * i <= x; ++i) if (x % i == 0) return false; return true; }
ll range_sum(ll a, ll b) {
	ll dif = a - 1, cnt = b - a + 1;
	ll ans = ((b - a + 1) * (b - a + 2)) / 2;
	ans += ((b - a + 1) * dif);
	return ans;
}
//void set_IO(string str = "") { if (!str.empty()) { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } }
void _print(long long t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << '"' << t << '"'; }
void _print(char t) { cerr << '\'' << t << '\''; }
void _print(double t) { cerr << t; }
void _print(long double t) { cerr << t; }
void _print(unsigned long long t) { cerr << t; }
void _print(bool t) { cerr << (t ? "true" : "false"); }
template<class T> void _print(vector<T> v) { cerr << "[ "; for (auto& i : v) { _print(i); cerr << " "; } cerr << "]"; }
template<class T, size_t N> void _print(array<T, N> a) { cerr << "[ "; for (auto& i : a) { _print(i); cerr << " "; } cerr << "]"; }
template<class T> void _print(set<T> v) { cerr << "{ "; for (auto& i : v) { _print(i); cerr << " "; } cerr << "}"; }
template<class T> void _print(multiset<T> v) { cerr << "{ "; for (auto& i : v) { _print(i); cerr << " "; } cerr << "}"; }
template<class T> void _print(unordered_set<T> v) { cerr << "{ "; for (auto& i : v) { _print(i); cerr << " "; } cerr << "}"; }
template<class T, class V> void _print(map<T, V> v) { cerr << "{ "; for (auto& i : v) { _print(i.first); cerr << ":"; _print(i.second); cerr << " "; } cerr << "}"; }
template<class T, class V> void _print(unordered_map<T, V> v) { cerr << "{ "; for (auto& i : v) { _print(i.first); cerr << ":"; _print(i.second); cerr << " "; } cerr << "}"; }
template<class T, class V> void _print(pair<T, V> p) { cerr << "("; _print(p.first); cerr << ", "; _print(p.second); cerr << ")"; }

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define dbg(x)
#endif

//#define blt __builtin_popcount
int blt(ll a) { int ans = 0; for (int i = 0; i <= 31; i++) if (a & (1ll << i)) ans++; return ans; }

int nxt(int A, int n) { return (A + 1 > n) ? (A + 1) % n : A + 1; }
int prv(int A, int n) { if (A == 1) return n; else if (A - 1 <= n) return A - 1; else return (A - 1) % n; }

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
mt19937 rnf(777);

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;
	//dp[2][0][0][a[2]][a[1]] = 2 - (a[1] == a[2]);
	//dp[2][a[2]][a[1]][0][0] = 2 - (a[1] == a[2]);
	///dp[2][a[1]][0][a[2]][0] = 2;
	//dp[2][a[2]][0][a[1]][0] = 2;
	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);
	int t = 1;
	//cin >> t;
	int T = t;
	while (t--) {
		cerr << "Test " << T - t << endl;
		solve();
		cout << endl;
	}
	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...