Submission #655331

#	Time	Username	Problem	Language	Result	Execution time	Memory
655331		Nakeeb	Miners (IOI07_miners)	C++17	84 / 100	1603 ms	235284 KiB

miners

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
map<string,int>mp;
int dp[100005][500];
int curr=1;
int func(string a,string b)
{
    if(mp[a+b])
        return mp[a+b];
    else 
        return mp[a+b]=curr++;
}
int solve(int i, string a, string b)
{
    if(i==n)
        return 0;
    if(~dp[i][func(a,b)])
        return dp[i][func(a,b)];
    string c="";
    c+=a[0],c+=a[1],c+=s[i];
    string d="";
    d+=b[0],d+=b[1],d+=s[i];
    int m=0,f=0,q=0;
    for(int i=0;i<3;i++)
    {
        if(c[i]=='M')
            m++;
        else if(c[i]=='F')
            f++;
        else if(c[i]=='B')
            q++;
    }
    string cc={c[1],c[2]};
    int c1=solve(i+1,cc,b)+min(m,1)+min(f,1)+min(q,1);
    m=0,f=0,q=0;
    for(int i=0;i<3;i++)
    {
        if(d[i]=='M')
            m++;
        else if(d[i]=='F')
            f++;
        else if(d[i]=='B')
            q++;
    }
    string dd={d[1],d[2]};
    int c2=solve(i+1,a,dd)+min(m,1)+min(f,1)+min(q,1);
    return dp[i][func(a,b)]=max(c1,c2);
}
int main()
{
    memset(dp,-1 ,sizeof(dp));
    cin>>n;
    cin>>s;
    cout<<solve(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: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8