oj.uz

Submission #655330

# Submission time Handle Problem Language Result Execution time Memory
655330 2022-11-03T20:45:03 Z Nakeeb Miners (IOI07_miners) C++17
100 / 100
 899 ms 141500 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100404 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100380 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100476 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100900 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 102540 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 104584 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 110740 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 131272 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 141500 KB Output is correct