제출 #1147081

#제출 시각아이디문제언어결과실행 시간메모리
1147081TsaganaMiners (IOI07_miners)C++20
9 / 100
1603 ms217312 KiB
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int n;
string s;
int a[100010];
int dp[100010][4][4][4][4];

int val(vector<int> v) {
	set<int> s;
	for (auto i: v) if (i) s.insert(i);
	return s.size();
}

int calc(int i, int a1, int a2, int b1, int b2) {
	if (i == n) return 0;
	if (~dp[i][a1][a2][b1][b2]) return dp[i][a1][a2][b1][b2];
	int x = val({a1, a2, a[i]}), y = val({b1, b2, a[i]});
	return max(calc(i+1, a[i], a1, b1, b2) + x, calc(i+1, a1, a2, a[i], b2) + y);
}

void solve () {
	memset(dp, -1, sizeof dp);
	cin >> n >> s;
	for (int i = 0; i < n; i++) a[i] = (s[i] == 'M' ? 1 : (s[i] == 'B' ? 2 : 3));
	cout << calc(0, 0, 0, 0, 0);
}
signed main() {IOS 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...