oj.uz

Submission #970475

# Submission time Handle Problem Language Result Execution time Memory
970475 2024-04-26T15:11:02 Z jadai007 Miners (IOI07_miners) C++14
100 / 100
 144 ms 1140 KB 
#include<bits/stdc++.h>

using namespace std;

int dp[2][4][4][4][4],n,arr[100001],ans = -1;
string s;

int cal(int i,int j,int k){
    int t=0;
    if(i==1||j==1||k==1)t++;
    if(i==2||j==2||k==2)t++;
    if(i==3||j==3||k==3)t++;
    return t;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>n>>s;
    for(int i = 1; i<=n; ++i){
        if(s[i-1]=='M') arr[i] = 1;
        else if(s[i-1]=='B') arr[i] = 2;
        else if(s[i-1]=='F') arr[i] = 3;
    }
    dp[0][arr[1]][0][0][0] = dp[0][0][0][arr[1]][0] = 1;
    for(int idx = 2; idx<=n; ++idx){
        int x = arr[idx];
        for(int i = 0; i<=3; ++i){
            for(int j = 0; j<=3; ++j){
                for(int k = 0; k<=3; ++k){
                    for(int l = 0; l<=3; ++l){
                        if(!dp[0][i][j][k][l]) continue;
                        dp[1][x][i][k][l] = max(dp[1][x][i][k][l], dp[0][i][j][k][l] + cal(x,i,j));
                        dp[1][i][j][x][k] = max(dp[1][i][j][x][k], dp[0][i][j][k][l] + cal(x,k,l));
                    }
                }
            }
        }
        for(int i = 0; i<=3; ++i){
            for(int j = 0; j<=3; ++j){
                for(int k = 0; k<=3; ++k){
                    for(int l = 0; l<=3; ++l){
                        dp[0][i][j][k][l] = dp[1][i][j][k][l];
                    }
                }
            }
        }
    }
    for(int i = 0; i<=3; ++i){
        for(int j = 0; j<=3; ++j){
            for(int k = 0; k<=3; ++k){
                for(int l = 0; l<=3; ++l){
                    ans = max(ans,  dp[1][i][j][k][l]);
                }
            }
        }
    }
    cout<<ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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