Submission #1126372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126372		AverageAmogusEnjoyer	Miners (IOI07_miners)	C++20	76 / 100	1607 ms	240580 KiB

miners

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

struct state {
    int a[3][2];
    bool operator==(const state &e) {
        for (int i=0;i<3;i++)
            for (int j=0;j<2;j++)
                if (a[i][j]!=e.a[i][j])
                    return 0;
        return 1;
    }
};

state shift(state &p,int w,int n) {
    state res = p;
    res.a[0][w]=res.a[1][w];
    res.a[1][w]=res.a[2][w];
    res.a[2][w]=n;
    return res;
}

int eval(state &s,int w) {
    int mask = 0;
    for (int i=0;i<3;i++)
        mask |= 1 << s.a[i][w];
    int ans = 0;
    for (int i=1;i<=3;i++)
        ans += (mask >> i) & 1;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;
    s = "#" + s;
    string wrs="BFM";
    vector<vector<pair<state,int>>> dp(n + 1);
    state def; memset(def.a,0,sizeof(def.a)); 
    dp[0].emplace_back(def,0);
    for (int i=1;i<=n;i++) {
        int v = find(wrs.begin(),wrs.end(),s[i])-wrs.begin() + 1;
        for (auto &[prev_state,val]: dp[i-1]) {
            for (int k=0;k<2;k++) {
                auto new_state = shift(prev_state,k,v);
                bool fnd=0;
                for (auto &[now,cval]: dp[i]) if (new_state == now) {
                    cmax(cval,val + eval(new_state,k));
                    fnd=1;
                    break;
                }
                if (!fnd) {
                    dp[i].emplace_back(new_state,val + eval(new_state,k));
                }
            }
        }
    }
    int ans = 0;
    for (auto &[s,val]: dp[n]) 
        cmax(ans,val);
    cout << ans << endl;
}

• 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: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8