This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |