제출 #1352379

#제출 시각아이디문제언어결과실행 시간메모리
1352379WarinchaiMiners (IOI07_miners)C++20
100 / 100
54 ms656 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int dp[2][4][4][4][4];
int inf=1e9;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    string s;cin>>s;
    for(int m=0;m<2;m++)for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)for(int l=0;l<4;l++)dp[m][i][j][k][l]=dp[m][i][j][k][l]=-inf;
    dp[0][0][0][0][0]=0;
    int cur=0;
    for(int i=0;i<n;i++){
        int val=0;
        if(s[i]=='M')val=1;
        else if(s[i]=='B')val=2;
        else val=3;
        cur^=1;
        for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)for(int l=0;l<4;l++)dp[cur][i][j][k][l]=-inf;
        for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)for(int l=0;l<4;l++){
            int cnt[4]={0,0,0,0};
            cnt[i]=1,cnt[j]=1,cnt[val]=1;
            int add=cnt[1]+cnt[2]+cnt[3];
            dp[cur][j][val][k][l]=max(dp[cur][j][val][k][l],dp[cur^1][i][j][k][l]+add);
            //
            cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
            cnt[k]=1,cnt[l]=1,cnt[val]=1;
            add=cnt[1]+cnt[2]+cnt[3];
            dp[cur][i][j][l][val]=max(dp[cur][i][j][l][val],dp[cur^1][i][j][k][l]+add);
        }
    }
    int ans=0;
    for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)for(int l=0;l<4;l++)ans=max(ans,dp[cur][i][j][k][l]);
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...