Submission #957550

#	Time	Username	Problem	Language	Result	Execution time	Memory
957550		hirayuu_oj	Miners (IOI07_miners)	C++17	92 / 100	426 ms	524288 KiB

miners

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,a,b) for(int i=a; i<(b); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;

int main(){
    int N;
    cin>>N;
    string S;
    cin>>S;
    rep(i,N){
        if(S[i]=='M'){
            S[i]='a';
        }
        if(S[i]=='F'){
            S[i]='b';
        }
        if(S[i]=='B'){
            S[i]='c';
        }
    }
    vector<vector<int>> dp(N+1,vector<int>(1600,-INF));
    dp[0][0]=0;
    array<string,40> ser;
    ser[0]="ddd";
    int cnt=1;
    rep(i,3){
        ser[cnt]="ddd";
        ser[cnt][2]='a'+i;
        cnt++;
        rep(j,3){
            ser[cnt]="ddd";
            ser[cnt][2]='a'+i;
            ser[cnt][1]='a'+j;
            cnt++;
            rep(k,3){
                ser[cnt]="ddd";
                ser[cnt][2]='a'+i;
                ser[cnt][1]='a'+j;
                ser[cnt][0]='a'+k;                
                cnt++;
            }
        }
    }
    array<int,64> num;
    array<int,64> score;
    array<int,40> fix;
    rep(i,40){
        num[(ser[i][0]-'a')+(ser[i][1]-'a')*4+(ser[i][2]-'a')*16]=i;
        fix[i]=(ser[i][0]-'a')+(ser[i][1]-'a')*4+(ser[i][2]-'a')*16;
        int cnt[4];
        cnt[0]=0;
        cnt[1]=0;
        cnt[2]=0;
        cnt[(ser[i][0]-'a')]++;
        cnt[(ser[i][1]-'a')]++;
        cnt[(ser[i][2]-'a')]++;
        score[(ser[i][0]-'a')+(ser[i][1]-'a')*4+(ser[i][2]-'a')*16]=0;
        if(cnt[0]!=0){
            score[(ser[i][0]-'a')+(ser[i][1]-'a')*4+(ser[i][2]-'a')*16]++;
        }
        if(cnt[1]!=0){
            score[(ser[i][0]-'a')+(ser[i][1]-'a')*4+(ser[i][2]-'a')*16]++;
        }
        if(cnt[2]!=0){
            score[(ser[i][0]-'a')+(ser[i][1]-'a')*4+(ser[i][2]-'a')*16]++;
        }
    }
    rep(i,N){
        rep(j,40){
            rep(k,40){
                if(dp[i][j*40+k]<=-INF)continue;
                int nj=fix[j]/4+(S[i]-'a')*16;
                int nk=fix[k]/4+(S[i]-'a')*16;
                dp[i+1][num[nj]*40+k]=max(dp[i+1][num[nj]*40+k],dp[i][j*40+k]+score[nj]);
                dp[i+1][j*40+num[nk]]=max(dp[i+1][j*40+num[nk]],dp[i][j*40+k]+score[nk]);
            }
        }
    }
    int ans=0;
    rep(i,1600){
        ans=max(ans,dp[N][i]);
    }
    cout<<ans<<"\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 0 / 8