Submission #582429

#	Time	Username	Problem	Language	Result	Execution time	Memory
582429		snasibov05	Miners (IOI07_miners)	C++14	100 / 100	932 ms	125760 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8