#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
// dp[i][a][b][c][d] i -> pos; a, b are last two in 1st mine, c, d- > second mine
// 0, 1, 2, 3
int to_int(char c){
return (c == 'M') ? 1 : ((c == 'F') ? 2 : 3);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin>>N;
string S;
cin>>S;
S = '*' + S;
ll dp[N+1][4][4][4][4];
memset(dp, 0, sizeof dp);
dp[0][0][0][0][0] = 0;
dp[1][to_int(S[1])][0][0][0] = 1;
dp[1][0][0][to_int(S[1])][0] = 1;
int freq[4];
freq[0] = inf;
freq[1] = freq[2] = freq[3] = 0;
freq[to_int(S[1])]++;
for(int i = 2; i <= N; ++i){
++freq[to_int(S[i])];
for(int a = 0; a < 4; ++a){
for(int b = 0; b < 4; ++b){
for(int c = 0; c < (b ? 4 : 1); ++c){
for(int d = 0; d < (a ? 4 : 1); ++d){
if((a == 0 and d != 0) || (b == 0 and c != 0)){
continue;
assert(false);
}
--freq[a];
--freq[b];
--freq[c];
--freq[d];
if(min({freq[0], freq[1], freq[2], freq[3]}) < 0){
++freq[a];
++freq[b];
++freq[c];
++freq[d];
continue;
}
++freq[a];
++freq[b];
++freq[c];
++freq[d];
set<int> SS;
for(int x : {a, d, to_int(S[i])}){
if(x != 0){
SS.insert(x);
}
}
dp[i][to_int(S[i])][a][b][c] = max(dp[i-1][a][d][b][c] + (ll)SS.size(), dp[i][to_int(S[i])][a][b][c]);
dp[i][b][c][to_int(S[i])][a] = max(dp[i-1][b][c][a][d] + (ll)SS.size(), dp[i][b][c][to_int(S[i])][a]);
}
}
}
}
}
// for(int i = 0; i <= N; ++i){
// for(int a = 0; a < 4; ++a){
// for(int b = 0; b < 4; ++b){
// for(int c = 0; c < 4; ++c){
// for(int d = 0; d < 4; ++d){
// cerr<<"dp["<<i<<"]["<<a<<"]["<<b<<"]["<<c<<"]["<<d<<"] = "<<dp[i][a][b][c][d]<<'\n';
// }
// }
// }
// }
// }
ll ans = 0;
for(int a = 0; a < 4; ++a){
for(int b = 0; b < 4; ++b){
for(int c = 0; c < 4; ++c){
for(int d = 0; d < 4; ++d){
if((a == 0 and d != 0) || (b == 0 and c != 0)){
continue;
}
ans = max(dp[N][a][b][c][d], ans);
}
}
}
}
cout<<ans<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
2284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
10496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
20588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
448 ms |
50668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1301 ms |
151016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1604 ms |
201064 KB |
Time limit exceeded |
