oj.uz

Submission #533608

# Submission time Handle Problem Language Result Execution time Memory
533608 2022-03-06T15:47:44 Z groshi Miners (IOI07_miners) C++17
100 / 100
 490 ms 374484 KB 
#include<iostream>
#include<map>
using namespace std;
int dp[100005][3][3][3][3][3][3];
bool odw[100005][3][3][3][3][3][3];
map<char,int> mapka;
int kub[3];
int n;
string s;
int reku(int i,int x1,int x2,int ile1,int y1,int y2,int ile2)
{
    if(i==n+1)
        return 0;
    if(odw[i][x1][x2][ile1][y1][y2][ile2])
        return dp[i][x1][x2][ile1][y1][y2][ile2];
    odw[i][x1][x2][ile1][y1][y2][ile2]=1;
    if(ile1>=1)
        kub[x1]=1;
    if(ile1>=2)
        kub[x2]=1;
    kub[mapka[s[i]]]=1;
    int mam=kub[0]+kub[1]+kub[2];
    kub[0]=0;
    kub[1]=0;
    kub[2]=0;
    dp[i][x1][x2][ile1][y1][y2][ile2]=max(dp[i][x1][x2][ile1][y1][y2][ile2],reku(i+1,mapka[s[i]],x1,min(ile1+1,2),y1,y2,ile2)+mam);

    if(ile2>=1)
        kub[y1]=1;
    if(ile2>=2)
        kub[y2]=1;
    kub[mapka[s[i]]]=1;
    mam=kub[0]+kub[1]+kub[2];
    kub[0]=0;
    kub[1]=0;
    kub[2]=0;
    dp[i][x1][x2][ile1][y1][y2][ile2]=max(dp[i][x1][x2][ile1][y1][y2][ile2],reku(i+1,x1,x2,ile1,mapka[s[i]],y1,min(ile2+1,2))+mam);
    return dp[i][x1][x2][ile1][y1][y2][ile2];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    cin>>s;
    s="0"+s;
    mapka['M']=0;
    mapka['B']=1;
    mapka['F']=2;
    cout<<reku(1,0,0,0,0,0,0);
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4044 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18964 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 37640 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 93764 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 280896 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 374484 KB Output is correct