/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
int n;
string s;
int a[N_MAX + 2];
int dp[N_MAX + 2][4][4][4][4];
int answer = 0;
void update (int &addr, int val) {
answer = max(answer, val);
addr = max(addr, val);
}
int f (int x, int y, int z) {
int vec[] = {x, y, z};
sort(vec, vec + 3);
if (vec[0] == 0) {
if (vec[1] == 0) {
return (vec[2] != 0);
} else {
return 1 + (vec[1] != vec[2]);
}
} else {
return 1 + (vec[0] != vec[1]) + (vec[1] != vec[2]);
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
cin >> s;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == 'M') {
a[i] = 1;
} else if (s[i - 1] == 'B') {
a[i] = 2;
} else {
a[i] = 3;
}
}
for (int i = 0; i <= n; i++) {
for (int x1 = 0; x1 <= 3; x1++) {
for (int y1 = 0; y1 <= 3; y1++) {
for (int x2 = 0; x2 <= 3; x2++) {
for (int y2 = 0; y2 <= 3; y2++) {
dp[i][x1][y1][x2][y2] = INT_MIN;
}
}
}
}
}
dp[0][0][0][0][0] = 0;
for (int i = 0; i < n; i++) {
for (int x1 = 0; x1 <= 3; x1++) {
for (int y1 = 0; y1 <= 3; y1++) {
for (int x2 = 0; x2 <= 3; x2++) {
for (int y2 = 0; y2 <= 3; y2++) {
int z = a[i + 1];
update(dp[i + 1][y1][z][x2][y2],
dp[i][x1][y1][x2][y2] + f(x1, y1, z));
update(dp[i + 1][x1][y1][y2][z],
dp[i][x1][y1][x2][y2] + f(x2, y2, z));
}
}
}
}
}
cout << answer << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
5344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
10392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
25536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
647 ms |
76020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
906 ms |
101188 KB |
Output is correct |