Submission #1178143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178143		AlgorithmWarrior	Miners (IOI07_miners)	C++20	100 / 100	167 ms	100644 KiB

miners

#include <bits/stdc++.h>

using namespace std;

int const INF=1000000000;
int const MAX=100005;
int dp[MAX][4][4][4][4];
int n;
char sir[MAX];
int distincte[4][4][4];

void read(){
    cin>>n;
    cin.get();
    cin.getline(sir+1,MAX);
    int i;
    for(i=1;i<=n;++i){
        if(sir[i]=='B') sir[i]=1;
        if(sir[i]=='F') sir[i]=2;
        if(sir[i]=='M') sir[i]=3;
    }
}

int distinct(int a,int b,int c){
    set<int>s;
    if(a)
        s.insert(a);
    if(b)
        s.insert(b);
    if(c)
        s.insert(c);
    return s.size();
}

void get_distincte(){
    int tip1,tip2,tip3;
    for(tip1=0;tip1<4;++tip1)
        for(tip2=0;tip2<4;++tip2)
            for(tip3=0;tip3<4;++tip3)
                distincte[tip1][tip2][tip3]=distinct(tip1,tip2,tip3);
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

int get_dp(){
    int i,tip,tip1,tip2,tip3,tip4;
    for(tip1=0;tip1<4;++tip1)
        for(tip2=0;tip2<4;++tip2)
            for(tip3=0;tip3<4;++tip3)
                for(tip4=0;tip4<4;++tip4)
                    dp[0][tip1][tip2][tip3][tip4]=-INF;
    dp[0][0][0][0][0]=0;
    for(i=1;i<=n;++i)
        for(tip1=0;tip1<4;++tip1)
            for(tip2=0;tip2<4;++tip2)
                for(tip3=0;tip3<4;++tip3)
                    for(tip4=0;tip4<4;++tip4){
                        dp[i][tip1][tip2][tip3][tip4]=-INF;
                        for(tip=0;tip<4;++tip){
                            if(tip1==sir[i])
                                maxself(dp[i][tip1][tip2][tip3][tip4],dp[i-1][tip2][tip][tip3][tip4]+distincte[tip1][tip2][tip]);
                            if(tip3==sir[i])
                                maxself(dp[i][tip1][tip2][tip3][tip4],dp[i-1][tip1][tip2][tip4][tip]+distincte[tip3][tip4][tip]);
                        }
                    }
    int ans=-INF;
    for(tip1=0;tip1<4;++tip1)
        for(tip2=0;tip2<4;++tip2)
            for(tip3=0;tip3<4;++tip3)
                for(tip4=0;tip4<4;++tip4)
                    maxself(ans,dp[n][tip1][tip2][tip3][tip4]);
    return ans;
}

int main()
{
    read();
    get_distincte();
    cout<<get_dp();
    return 0;
}

• 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