oj.uz

Submission #584123

# Submission time Handle Problem Language Result Execution time Memory
584123 2022-06-26T20:20:08 Z AtinaR Miners (IOI07_miners) C++14
100 / 100
 815 ms 210284 KB 
#include <bits/stdc++.h>

using namespace std;
const long long MAX=100001;
long long n;
string s;
long long dp[MAX][4][4][4][4];
long long check(long long a, long long b, long long c)
{
    set<long long> st;
    if(a!=0)st.insert(a);
    if(b!=0)st.insert(b);
    if(c!=0)st.insert(c);
    return st.size();
}
long long rek(long long i, long long L1,long long L2, long long R1, long long R2)
{
    if(i==n)
    {
       return 0;
    }
    long long res=0;
    if(dp[i][L1][L2][R1][R2]!=-1)return dp[i][L1][L2][R1][R2];
    long long tmp;
    if(s[i]=='M')
    {
        tmp=1;
    }
    else if(s[i]=='B')
    {
        tmp=2;
    }
    else
    {
        tmp=3;
    }
    res=rek(i+1,tmp,L1, R1, R2)+check(tmp,L1,L2);
    res=max(res,rek(i+1,L1,L2,tmp,R1)+check(tmp,R1,R2));
    return dp[i][L1][L2][R1][R2]=res;
}
int32_t main()
{
    cin>>n;
    cin>>s;
    memset(dp,-1,sizeof(dp));
    cout<<rek(0,0,0,0,0)<<endl;
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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