oj.uz

Submission #448090

# Submission time Handle Problem Language Result Execution time Memory
448090 2021-07-28T20:27:29 Z Deepesson Miners (IOI07_miners) C++17
100 / 100
 503 ms 371724 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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