#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array
const int INF = 1e17;
const int MOD = 998244353;
const int MXN = 1e5+9;
int dp[MXN][3][3][3][3];
void amax(int &a, int b) { a = max(a, b); }
int distinct(int i, int j, int k) {
int ans = 0;
for (int x = 0; x < 3; x++)
if (i == x || j == x || k == x) ans++;
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie();
int n; string s; cin>>n>>s;
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
for (int l = 0; l < 3; l++)
for (int m = 0; m < 3; m++)
dp[0][j][k][l][m] = -6;
int ans = -INF;
for (int i = 1; i <= n; i++) {
int cur = -1;
if (s[i-1] == 'M') cur = 0;
if (s[i-1] == 'F') cur = 1;
if (s[i-1] == 'B') cur = 2;
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
for (int l = 0; l < 3; l++)
for (int m = 0; m < 3; m++)
dp[i][j][k][l][m] = -INF;
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
for (int l = 0; l < 3; l++) {
for (int m = 0; m < 3; m++) {
int x1 = distinct(j, k, cur);
int x2 = distinct(l, m, cur);
amax(dp[i][k][cur][l][m], dp[i-1][j][k][l][m] + x1);
amax(dp[i][j][k][m][cur], dp[i-1][j][k][l][m] + x2);
amax(ans, dp[i][k][cur][l][m]);
amax(ans, dp[i][j][k][m][cur]);
}
}
}
}
}
cout<<ans<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 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 |
204 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 |
2 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
3436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
6596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
16128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
47956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
63852 KB |
Output is correct |