#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
const int N = 100001;
int n, dp[N][4][4][4][4];
string s;
int id(char c){
if(c == 'M') return 0;
if(c == 'B') return 1;
if(c == 'F') return 2;
assert(false);
}
int diff(int x, int y, int z){
set <int> ret = {x, y, z};
while(*ret.rbegin() == 3){
ret.erase(--ret.end());
}
return ret.size();
}
int solve(int ind, int p11, int p12, int p21, int p22){
if(ind == n) return 0;
int &ret = dp[ind][p11][p12][p21][p22];
if(ret != -1) return ret;
int one = diff(id(s[ind]), p11, p12) + solve(ind + 1, id(s[ind]), p11, p21, p22);
int two = diff(id(s[ind]), p21, p22) + solve(ind + 1, p11, p12, id(s[ind]), p21);
return ret = max(one, two);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof dp);
cin >> n >> s;
cout << solve(0, 3, 3, 3, 3) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
100600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
100600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
100600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
100600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
100516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
100456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
100640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
100956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
101376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
102520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
597 ms |
106700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1256 ms |
108732 KB |
Output is correct |