Submission #1291578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291578		qrn	Miners (IOI07_miners)	C++20	0 / 100	1602 ms	177568 KiB

miners

// perhaps one does not have a choice when he does not enjoy anything, so he just yaps to himself in vsc like a loser.
// ome47

#include "bits/stdc++.h"
using namespace std;
#define intt long long

const intt mxN = 2e5 + 5;
const intt LG = 20;
const intt inf = 1e18;

string s;
intt n;

intt dp[mxN][4][4][4][4];

intt delta(intt a, intt b, intt c) {
    set<intt> st;
    st.insert(a); st.insert(b); st.insert(c);
    return st.size() - (a == 0 || b == 0 || c == 0);
}

void _() {
    cin >> n >> s;

    vector<intt> a(n);
    for(intt i = 0; i < n; i++) {
        if(s[i] == 'M') a[i] = 1;
        if(s[i] == 'B') a[i] = 2;
        if(s[i] == 'F') a[i] = 3;
    }

    dp[0][a[0]][0][0][0] = 1;
    dp[0][0][0][a[0]][0] = 1;
    for(intt i = 1; i < n; i++) {
        for(intt f1 = 0; f1 < 4; f1++) {
            for(intt f2 = 0; f2 < 4; f2++) {
                for(intt s1 = 0; s1 < 4; s1++) {
                    for(intt s2 = 0; s2 < 4; s2++) {
                        if(!dp[i-1][f1][f2][s1][s2])
                        dp[i][a[i]][f1][s1][s2] = max(dp[i][a[i]][f1][s1][s2], dp[i-1][f1][f2][s1][s2] + delta(a[i], f1, f2));
                        dp[i][f1][f2][a[i]][s1] = max(dp[i][f1][f2][a[i]][s1], dp[i-1][f1][f2][s1][s2] + delta(a[i], s1, s2));
                    }
                }
            }
        }
    }

    intt ans = 0;
    for(intt f1 = 0; f1 < 4; f1++) {
        for(intt f2 = 0; f2 < 4; f2++) {
            for(intt s1 = 0; s1 < 4; s1++) {
                for(intt s2 = 0; s2 < 4; s2++) {
                    ans = max(ans, dp[n-1][f1][f2][s1][s2]);
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    intt t = 1;
    // cin >> t;
    while(t--){
        // cout << endl;
        _();
    }
}
// ⠀⠀⠀⠀⠀⠀⠀⢀⣤⣦⣶⣤⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣤⢀⣀⡀⣠⣄⣠⣶⣿⣿⣿⣿⣿⣿⣿⣷⣾⡦⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠻⡳⢛⠛⠒⠚⢛⣿⣿⠟⠋⠉⠛⠛⢿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀
// ⢛⡛⢿⣿⠟⠻⠛⣿⣇⣶⣖⣤⣀⣄⡰⣹⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀
// ⢿⠿⠿⠿⠿⠿⠿⢭⣐⠠⢼⣬⠽⢈⢁⡿⠛⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣛⣱⣤⣤⣤⣀⣄⣄⣗⢌⠋⠉⢙⣴⣧⢤⣤⣤⣤⣦⡀⠀⠀⠀⠀⢺⡿
// ⣿⣿⣿⠟⠛⠋⠀⡬⠼⢠⠍⠂⠀⠨⡇⠀⡏⠉⠛⢿⣧⠀⠀⠀⠀⢸⣀
// ⣟⠄⠀⠀⠀⠀⠀⢡⠀⠀⠀⠀⠀⡠⠁⢀⠁⠀⠀⠀⠘⣗⢀⠄⢶⣼⣾
// ⠀⠀⠀⢠⣦⠇⠀⠀⠁⠒⠒⠒⠈⠀⠀⠀⣞⢶⡀⠀⠀⠹⣧⣠⡞⣸⣏
// ⠀⠀⢀⡞⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣦⡀⠀⠈⠫⣕⣻⡇
// ⠀⠀⣾⣧⠈⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⣿⣿⣿⣷⣦⡠⡤⠀⣿⡇
// ⠠⢿⣿⣿⠂⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠴⣿⣿⣿⣿⠟⠋⢀⣤⣿⣷
// ⣀⣀⣀⣙⣃⣠⣤⣔⣤⣢⣵⣒⣒⣢⣄⣤⣄⣛⣋⣉⣀⣀⣤⣿⣿⣿⣿

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8