oj.uz

Submission #584114

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

using namespace std;
const int MAX=1e5+10;
int n;
string s;
int dp[MAX][4][4][4][4];
int check(int a, int b, int c)
{
    set<int> st;
    if(a!=0)st.insert(a);
    if(b!=0)st.insert(b);
    if(c!=0)st.insert(c);
    return st.size();
}
int rek(int i, int L1,int L2, int R1, int R2)
{
    if(i==n)
    {
       return 0;
    }
    int res=0;
    if(dp[i][L1][R1][L2][R2]!=-1)return dp[i][L1][L2][R1][R2];
    int 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 37 ms 100428 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 100536 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 1588 ms 100980 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 1593 ms 101684 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 1595 ms 103244 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 1582 ms 108852 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 1593 ms 111692 KB Time limit exceeded
2 Halted 0 ms 0 KB -