Submission #1126373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126373		AverageAmogusEnjoyer	Miners (IOI07_miners)	C++20	100 / 100	818 ms	100948 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;
}

const int N=100100;
const int K=8;
int dp[N][1 << K];

int get_bit(int v,int k) {
    return (v >> k) & 1;
}

int eval(int v,int k,int n) {
    // cout << bitset<8>(v) << " and " << k << " becomes ";
    if (k)
        v = v >> 4;
    // cout << bitset<4>(v) << endl;
    int mask = (1 << (get_bit(v,0) + 2 * get_bit(v,1))) | (1 << (get_bit(v,2) + 2 * get_bit(v,3))) | (1 << n);
    return get_bit(mask,1) + get_bit(mask,2) + get_bit(mask,3);
}

int bts[8];

int insert(int v,int k,int n) {
    for (int i=0;i<8;i++) 
        bts[i]=get_bit(v,i);
    if (k) {
        bts[4]=bts[6],bts[5]=bts[7],bts[6]=get_bit(n,0),bts[7]=get_bit(n,1);
        int res=0;
        for (int i=0;i<8;i++)
            res|=bts[i]*(1<<i);
        return res;
    } else {
        bts[4-4]=bts[6-4],bts[5-4]=bts[7-4],bts[6-4]=get_bit(n,0),bts[7-4]=get_bit(n,1);
        int res=0;
        for (int i=0;i<8;i++)
            res|=bts[i]*(1<<i);        
        return res;
    }
}

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

    int n;
    cin >> n;
    string s;
    cin >> s;
    s = "#" + s;
    string wrs="BFM";
    memset(dp,0xc0,sizeof(dp));
    dp[0][0]=0;
    for (int i=1;i<=n;i++) {
        int v = find(wrs.begin(),wrs.end(),s[i])-wrs.begin() + 1;
        for (int prev_state=0;prev_state<(1<<K);prev_state++) {
            for (int k=0;k<2;k++) {
                auto new_state = insert(prev_state,k,v);
                // cout << bitset<8>(prev_state) << " " << k << " " << v << " " << bitset<8>(new_state) << " " << eval(prev_state,k,v) << endl;
                cmax(dp[i][new_state],dp[i-1][prev_state] + eval(prev_state,k,v));
            }
        }
    }
    int ans=0;
    for (int i=0;i<(1<<K);i++)
        cmax(ans,dp[n][i]);
    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: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8