oj.uz

Submission #582429

# Submission time Handle Problem Language Result Execution time Memory
582429 2022-06-23T18:32:23 Z snasibov05 Miners (IOI07_miners) C++14
100 / 100
 932 ms 125760 KB 
#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5 + 5;
int dp[mx][4][4][4][4];
bool v[mx][4][4][4][4];
map<char, int> mp;

int cnt(int l1, int l2, char c){
    set<int> st;
    if (l1 != 0) st.insert(l1);
    if (l2 != 0) st.insert(l2);
    st.insert(mp[c]);
    return st.size();
}

int main() {
    int n; cin >> n;
    string str; cin >> str;

    mp['B'] = 1, mp['F'] = 2, mp['M'] = 3;

    v[0][0][0][0][0] = true;
    for (int i = 0; i < n; ++i){
        for (int l11 = 0; l11 < 4; ++l11){
            for (int l12 = 0; l12 < 4; ++l12){
                for (int l21 = 0; l21 < 4; ++l21){
                    for (int l22 = 0; l22 < 4; ++l22){
                        if (!v[i][l11][l12][l21][l22]) continue;

                        dp[i+1][l12][mp[str[i]]][l21][l22] = max(dp[i+1][l12][mp[str[i]]][l21][l22], dp[i][l11][l12][l21][l22] + cnt(l11, l12, str[i]));
                        v[i+1][l12][mp[str[i]]][l21][l22] = true;

                        dp[i+1][l11][l12][l22][mp[str[i]]] = max(dp[i+1][l11][l12][l22][mp[str[i]]], dp[i][l11][l12][l21][l22] + cnt(l21, l22, str[i]));
                        v[i+1][l11][l12][l22][mp[str[i]]] = true;
                    }
                }
            }
        }
    }

    int MX = 0;
    for (int l11 = 0; l11 < 4; ++l11){
        for (int l12 = 0; l12 < 4; ++l12){
            for (int l21 = 0; l21 < 4; ++l21){
                for (int l22 = 0; l22 < 4; ++l22){
                    if (!v[n][l11][l12][l21][l22]) continue;
                    MX = max(MX, dp[n][l11][l12][l21][l22]);
                }
            }
        }
    }

    cout << MX << "\n";

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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