oj.uz

Submission #397238

# Submission time Handle Problem Language Result Execution time Memory
397238 2021-05-01T18:25:52 Z AugustinasJucas Miners (IOI07_miners) C++14
100 / 100
 1006 ms 100696 KB 
#include <bits/stdc++.h>

using namespace std;
int n;
string a;
int hsh(char a){
    if(a == 'M') return 1;
    if(a == 'B') return 2;
    if(a == 'F') return 3;
    return 0;
}
const int dydis = 1e5+10;
const int inf = 1e9;
int dp[dydis][4][4][4][4];
int kek(int a, int b, int c){
    set<int> st = {a, b, c};
    return st.size() - st.count(0);
}
int main(){
    for(int i = 0; i < dydis; i++){
        for(int j = 0; j < 4; j++){
            for(int h = 0; h < 4; h++){
                for(int l = 0; l < 4; l++){
                    for(int g = 0; g < 4; g++){
                        dp[i][j][h][l][g] = -inf;
                    }
                }
            }
        }
    }
    cin >> n >> a;
    dp[0][0][0][0][0] = 0;

    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            for(int h = 0; h < 4; h++){
                for(int l = 0; l < 4; l++){
                    for(int g = 0; g < 4; g++){
                        if(dp[i][j][h][l][g] < 0) continue;
                        dp[i+1][h][hsh(a[i])][l][g] = max(dp[i+1][h][hsh(a[i])][l][g], dp[i][j][h][l][g] + kek(j, h, hsh(a[i])));
                        dp[i+1][j][h][g][hsh(a[i])] = max(dp[i+1][j][h][g][hsh(a[i])], dp[i][j][h][l][g] + kek(l, g, hsh(a[i])));
                        ans = max(ans, dp[i+1][h][hsh(a[i])][l][g]);
                        ans = max(ans, dp[i+1][j][h][g][hsh(a[i])]);                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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