oj.uz

Submission #655331

# Submission time Handle Problem Language Result Execution time Memory
655331 2022-11-03T20:52:42 Z Nakeeb Miners (IOI07_miners) C++17
84 / 100
 1500 ms 235284 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 195948 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 195944 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 195868 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 195936 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 195968 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 195944 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 196372 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 197956 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 199924 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 205828 KB Output is correct

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1572 ms 225524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1603 ms 235284 KB Time limit exceeded
2 Halted 0 ms 0 KB -