oj.uz

Submission #584116

# Submission time Handle Problem Language Result Execution time Memory
584116 2022-06-26T19:49:08 Z AtinaR Miners (IOI07_miners) C++14
52 / 100
 1500 ms 210400 KB 
#include <bits/stdc++.h>

using namespace std;
const long long MAX=1e5+1;
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][R1][L2][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;
}
int 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 79 ms 200644 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1570 ms 200760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 201080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 201552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 203044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 207940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 210400 KB Time limit exceeded
2 Halted 0 ms 0 KB -