Submission #957555

#	Time	Username	Problem	Language	Result	Execution time	Memory
957555		hirayuu_oj	Miners (IOI07_miners)	C++17	100 / 100	276 ms	728 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<int> dp(1600,-INF);
    dp[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){
        vector<int> ndp(1600,-INF);
        rep(j,40){
            rep(k,40){
                if(dp[j*40+k]<=-INF)continue;
                int nj=fix[j]/4+(S[i]-'a')*16;
                int nk=fix[k]/4+(S[i]-'a')*16;
                ndp[num[nj]*40+k]=max(ndp[num[nj]*40+k],dp[j*40+k]+score[nj]);
                ndp[j*40+num[nk]]=max(ndp[j*40+num[nk]],dp[j*40+k]+score[nk]);
            }
        }
        dp=move(ndp);
    }
    int ans=0;
    rep(i,1600){
        ans=max(ans,dp[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: 8 / 8