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;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
string opt="XMFB";
vector<string> st;
map<string,int> h;
for(int a=0;a<4;a++)
{
for(int b=0;b<4;b++)
{
for(int c=0;c<4;c++)
{
bool ok=1;
bool nonx=0;
for(int x:{c,b,a})
{
nonx|=(x!=0);
if(x==0) ok&=(!nonx);
}
if(ok)
{
string t=string(1,opt[a])+string(1,opt[b])+string(1,opt[c]);
h[t]=st.size();
st.push_back(t);
}
}
}
}
const int N=40;
vector<int> score(N,0);
for(int i=0;i<N;i++)
{
set<char> tmp;
for(char c:st[i]) if(c!='X') tmp.insert(c);
score[i]=tmp.size();
}
vector<array<int,3>> mv(N,{-1,-1,-1});
for(int i=0;i<N;i++)
{
for(int j=1;j<=3;j++)
{
string tmp=opt[j]+st[i];
tmp.pop_back();
mv[i][j]=h[tmp];
}
}
const int inf=(1<<30);
vector dp(N,vector(N,int(-inf)));
dp[0][0]=0;
auto chmax=[&](int &a,int b){a=max(a,b);};
string s;
cin >> s;
for(char c:s)
{
vector ndp(N,vector(N,int(-inf)));
int t=opt.find(c);
for(int j=0;j<N;j++)
{
for(int k=0;k<N;k++)
{
int nj=mv[j][t];
chmax(ndp[nj][k],dp[j][k]+score[nj]);
int nk=mv[k][t];
chmax(ndp[j][nk],dp[j][k]+score[nk]);
}
}
dp=ndp;
}
int res=0;
for(int i=0;i<N;i++) for(int j=0;j<N;j++) chmax(res,dp[i][j]);
cout << res << "\n";
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... |