Submission #584117

#	Time	Username	Problem	Language	Result	Execution time	Memory
584117		AtinaR	Miners (IOI07_miners)	C++14	52 / 100	1610 ms	210256 KiB

miners

#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][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;
}
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 / 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