Submission #448090

#	Time	Username	Problem	Language	Result	Execution time	Memory
448090		Deepesson	Miners (IOI07_miners)	C++17	100 / 100	503 ms	371724 KiB

miners

#include <bits/stdc++.h>
#define MAX 110000
int array[MAX];
bool existe[MAX][3][3][3][3][3][3];
int tab[MAX][3][3][3][3][3][3];
typedef std::pair<int,int> prev;
int N;
int dp(int pos,int v1,int v2,int v3,int v4,int v5,int v6){
    if(pos==N)return 0;
    if(existe[pos][v1][v2][v3][v4][v5][v6])return tab[pos][v1][v2][v3][v4][v5][v6];
    existe[pos][v1][v2][v3][v4][v5][v6]=true;
    int best = 0;
    ///Mina 1
    {
        bool diferentes[3]={};
        if(v3)diferentes[v1]=true;
        if(v3>1)diferentes[v2]=true;
        diferentes[array[pos]]=true;
        int bonus = diferentes[0] + diferentes[1] + diferentes[2];
        best = std::max(best,bonus+
                        dp(pos+1,array[pos],v1,std::min(v3+1,2),v4,v5,v6));
    }
    {
        bool diferentes[3]={};
        if(v6)diferentes[v4]=true;
        if(v6>1)diferentes[v5]=true;
        diferentes[array[pos]]=true;
        int bonus = diferentes[0] + diferentes[1] + diferentes[2];
        best = std::max(best,bonus+
                        dp(pos+1,v1,v2,v3,array[pos],v4,std::min(v6+1,2)));
    }
    return tab[pos][v1][v2][v3][v4][v5][v6]=best;
}
int main()
{
    std::cin>>N;
    std::string s;
    std::cin>>s;
    for(int i=0;i!=N;++i){
        if(s[i]=='B')array[i]=0;
        else if(s[i]=='F')array[i]=1;
        else array[i]=2;
    }
    std::cout << dp(0,0,0,0,0,0,0) << "\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