Submission #655330

#	Time	Username	Problem	Language	Result	Execution time	Memory
655330		Nakeeb	Miners (IOI07_miners)	C++17	100 / 100	899 ms	141500 KiB

miners

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
map<char,int>mp;
int dp[100005][4][4][4][4];
int solve(int i, string a, string b)
{
    int in1=mp[a[0]],in2=mp[a[1]],in3=mp[b[0]],in4=mp[b[1]];
    if(i==n)
        return 0;
    if(~dp[i][in1][in2][in3][in4])
        return dp[i][in1][in2][in3][in4];
    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][in1][in2][in3][in4]=max(c1,c2);
}
int main()
{
    memset(dp,-1 ,sizeof(dp));
    mp['.']=0;
    mp['M']=1;
    mp['F']=2;
    mp['B']=3;
    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: 8 / 8
• Subtask 12: 8 / 8