Submission #1232478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232478		countless	Miners (IOI07_miners)	C++20	91 / 100	616 ms	190872 KiB

miners

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"
#define rep(i, a, b) for (ll i = a; i < b; i++)

const ll INF = 1e18;
const int MAXN = 1e5+5;

using state = tuple<ll, ll, ll>;
state dp[MAXN][3][3][3][3];

void solve() {
    int n; cin >> n;
    string s; cin >> s;

    map<int, char> wrd;
    map<char, int> rev;
    wrd[0] = 'M', wrd[1] = 'F', wrd[2] = 'B';
    rev['M'] = 0, rev['F'] = 1, rev['B'] = 2;

    // fill_n(&dp[0][0][0][0][0], MAXN*3*3*3*3, make_tuple(-INF, 0, 0));
    rep(i,0,n) rep(l1,0,3) rep(l2,0,3) rep(r1,0,3) rep(r2,0,3) {
        if (i == 0) dp[i][l1][l2][r1][r2] = make_tuple(0, 0, 0);
        else dp[i][l1][l2][r1][r2] = make_tuple(-INF, 0, 0);
    }

    rep(i,0,n) {
        int tng = rev[s[i]];
        rep(m,0,2) rep(l1,0,3) rep(l2,0,3) rep(r1,0,3) rep(r2,0,3) {
            auto [cand, c1, c2] = dp[i][l1][l2][r1][r2];

            set<int> amt;
            if (m == 0) {
                amt.insert(tng);
                if (c1 >= 1) amt.insert(l1);
                if (c1 >= 2) amt.insert(l2);
                
                dp[i+1][tng][l1][r1][r2] = max(dp[i+1][tng][l1][r1][r2], make_tuple(cand + ll(amt.size()), c1 + 1, c2));
            } else {
                amt.insert(tng);
                if (c2 >= 1) amt.insert(r1);
                if (c2 >= 2) amt.insert(r2);
                
                dp[i+1][l1][l2][tng][r1] = max(dp[i+1][l1][l2][tng][r1], make_tuple(cand + ll(amt.size()), c1, c2 + 1));
            }
        }
    }

    ll ans = 0;
    rep(l1,0,3) rep(l2,0,3) rep(r1,0,3) rep(r2,0,3) {
        ans = max(ans, get<0>(dp[n][l1][l2][r1][r2]));
    }

    cout << ans << endl;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 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