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 m_p make_pair
const int N=100005;
const int INF=1000000000;
int n;
char a[N];
int dp[4][4][4][4];
int ydp[4][4][4][4];
int main()
{
//freopen("input.txt","r",stdin);
cin>>n;
cin>>a;
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
dp[x1][y1][x2][y2]=-INF;
dp[3][3][3][3]=0;
for(int i=1;i<=n;++i)
{
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
ydp[x1][y1][x2][y2]=-INF;
int z;
if(a[i-1]=='M')
z=0;
else if(a[i-1]=='B')
z=1;
else
z=2;
for(int x1=0;x1<4;++x1)
{
for(int y1=0;y1<4;++y1)
{
for(int x2=0;x2<4;++x2)
{
for(int y2=0;y2<4;++y2)
{
int b[4]={};
b[x1]=1;
b[y1]=1;
b[z]=1;
ydp[y1][z][x2][y2]=max(ydp[y1][z][x2][y2],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]);
b[0]=0;
b[1]=0;
b[2]=0;
b[x2]=1;
b[y2]=1;
b[z]=1;
ydp[x1][y1][y2][z]=max(ydp[x1][y1][y2][z],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]);
}
}
}
}
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
dp[x1][y1][x2][y2]=ydp[x1][y1][x2][y2];
}
int ans=-INF;
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
ans=max(ans,dp[x1][y1][x2][y2]);
cout<<ans<<endl;
return 0;
}
# | 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... |