Submission #941892

#	Time	Username	Problem	Language	Result	Execution time	Memory
941892		prairie2022	Boarding Passes (BOI22_passes)	C++17	100 / 100	151 ms	15196 KiB

passes

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

int main(){
    cin.tie(0)->sync_with_stdio(0);
    const int G = 15;
    vector<int> seat[G];
    vector<ll> cross[G][G]; // [j][g] = j crosses g

    { // total crosses needed
        string s;
        cin >> s;
        int n = s.size();
        for(int i=0; i<n; i++) seat[s[i]-'A'].push_back(i+1);
        
        vector<int> pre(n+1);
        for(int g=0; g<G; g++){
            pre[0] = 0;
            for(int i=0; i<n; i++)
                pre[i+1] = pre[i]+(s[i]=='A'+g);
            for(int j=0; j<G; j++){
                auto &v = cross[j][g];
                v = {0};
                for(const int i : seat[j]) v.push_back(v.back()+pre[i]);
            }
            pre[n] = 0;
            for(int i=n-1; ~i; i--) pre[i] = pre[i+1]+(s[i]=='A'+g);
            for(int j=0; j<G; j++){
                auto &v  = cross[j][g];
                ll suf = 0;
                for(int i=(int)seat[j].size()-1; ~i; i--)
                    v[i] += (suf += pre[seat[j][i]-1]);
            }

            for(int j=0; j<G; j++){
                if(j==g){
                    for(auto &c: cross[j][g]) c -= seat[j].size();
                }
                else{
                    for(auto &c: cross[j][g]) c <<= 1;
                }
            }
        }
    }

    ll dp[1<<G];
    memset(dp, 0x3f, sizeof(dp));

    auto E = [&](int mask, int g)->ll{
        auto cost = [&](int i)->ll{
            ll ans = 0;
            for(int j=0; j<G; j++){
                if((mask>>j)&1) ans += cross[g][j][i];
            }
            return ans;
        };
        int l = 0, r = seat[g].size();
        while(l<r){
            int mid = (l+r)>>1;
            if(cost(mid+1)>cost(mid)) r = mid;
            else l = mid+1;
        }
        return cost(l);
    };
    dp[0] = 0;
    for(int mask = 1; mask<(1<<G); mask++){
        for(int g=0; g<G; g++){
            if((mask>>g)&1) dp[mask] = min(dp[mask], dp[mask^(1<<g)]+E(mask, g));
        }
    }
    ll ans = dp[(1<<G)-1];
    if(ans&1) cout << (ans>>1) << ".5\n";
    else cout << (ans>>1) << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40