Submission #584114

#	Time	Username	Problem	Language	Result	Execution time	Memory
584114		AtinaR	Miners (IOI07_miners)	C++14	52 / 100	1595 ms	111692 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8