oj.uz

Submission #957550

# Submission time Handle Problem Language Result Execution time Memory
957550 2024-04-04T02:59:20 Z hirayuu_oj Miners (IOI07_miners) C++17
92 / 100
 426 ms 524288 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31836 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 63480 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 158024 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 472968 KB Output is correct

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 236 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -