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;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e5+50;
int n,t[nax];
string s;
ll dp[nax][4][4][4][4];
ll calc(int idx,pair<int,int> a,pair<int,int> b){
if(idx == n)
return 0;
ll &ret = dp[idx][a.first][a.second][b.first][b.second];
if(ret != -1)
return ret;
int add = 1;
if(a.first != 0 && a.first != t[idx])
add++;
if(a.second != 0 && a.second != a.first && a.second != t[idx])
add++;
ret = calc(idx+1,{a.second,t[idx]},b) + add;
add = 1;
if(b.first != 0 && b.first != t[idx])
add++;
if(b.second != 0 && b.second != b.first && b.second != t[idx])
add++;
ret = max(ret,calc(idx+1,a,{b.second,t[idx]}) + add);
return ret;
}
int main(){
memset(dp,-1,sizeof(dp));
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i] == 'M')t[i] = 1;
if(s[i] == 'F')t[i] = 2;
if(s[i] == 'B')t[i] = 3;
}
cout << calc(0,{0,0},{0,0}) << endl;
}
# | 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... |