oj.uz

Submission #432790

# Submission time Handle Problem Language Result Execution time Memory
432790 2021-06-18T13:23:04 Z tengiz05 Miners (IOI07_miners) C++17
100 / 100
 386 ms 101184 KB 
#include <bits/stdc++.h>
constexpr int N = 100000;
int dp[N][4][4][4][4];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = std::string("MFB").find(s[i]) + 1;
    }
    memset(dp, 190, sizeof dp);
    dp[0][0][a[0]][0][0] = 1;
    dp[0][0][0][0][a[0]] = 1;
    for (int p = 1; p < n; p++) {
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                for (int I = 0; I < 4; I++)
                    for (int J = 0; J < 4; J++)
                        dp[p][i][j][I][J] = dp[p - 1][i][j][I][J];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int I = 0; I < 4; I++) {
                    for (int J = 0; J < 4; J++) {
                        int cost;
                        if (i == 0 && j == 0) cost = 1;
                        else if (i == 0 || j == 0) cost = 1 + ((i ^ j) != a[p]);
                        else if (i == j && j == a[p]) cost = 1;
                        else if (i == j || j == a[p] || i == a[p]) cost = 2;
                        else cost = 3;
                        dp[p][j][a[p]][I][J] = std::max(dp[p][j][a[p]][I][J], dp[p - 1][i][j][I][J] + cost);
                        if (I == 0 && J == 0) cost = 1;
                        else if (I == 0 || J == 0) cost = 1 + ((I ^ J) != a[p]);
                        else if (I == J && J == a[p]) cost = 1;
                        else if (I == J || J == a[p] || I == a[p]) cost = 2;
                        else cost = 3;
                        dp[p][i][j][J][a[p]] = std::max(dp[p][i][j][J][a[p]], dp[p - 1][i][j][I][J] + cost);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            for (int I = 0; I < 4; I++)
                for (int J = 0; J < 4; J++)
                    ans = std::max(ans, dp[n - 1][i][j][I][J]);
    std::cout << ans << "\n";
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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