Submission #580104

#	Time	Username	Problem	Language	Result	Execution time	Memory
580104		wiwiho	Boarding Passes (BOI22_passes)	C++14	100 / 100	194 ms	13388 KiB

passes

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

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

    string s;
    cin >> s;
    int n = s.size();
    const int G = 15;

    vector<vector<int>> pos(G, vector<int>(1));
    vector<int> id(n);
    for(int i = 0; i < n; i++){
        id[i] = pos[s[i] - 'A'].size();
        pos[s[i] - 'A'].eb(i);
    }
    
    vector<vector<vector<ll>>> f(G, vector<vector<ll>>(G));
    for(int a = 0; a < G; a++){
        for(int b = 0; b < G; b++){
            f[a][b].resize(pos[a].size() + 1);

            ll total = 0;
            ll cnt = 0;
            for(int i = 0; i < n; i++){
                if(s[i] == 'A' + a){
                    total += cnt;
                    f[a][b][id[i]] += total;
                }
                if(s[i] == 'A' + b) cnt++;
            }

            total = 0;
            cnt = 0;
            for(int i = n - 1; i >= 0; i--){
                if(s[i] == 'A' + a){
                    f[a][b][id[i]] += total;
                    total += cnt;
                }
                if(s[i] == 'A' + b) cnt++;
            }
            f[a][b][0] = total;
        }
    }

    auto fmsk = [&](int a, int msk, int i){
        ll ans = 0;
        for(int j = 0; j < G; j++){
            if(1 << j & msk) ans += f[a][j][i];
        }
        return 2 * ans + f[a][a][i];
    };

    auto best = [&](int a, int msk){
        int l = 0, r = pos[a].size(); r--;
        while(l < r){
            int mid = (l + r) / 2;
            if(fmsk(a, msk, mid) >= fmsk(a, msk, mid + 1)) l = mid + 1;
            else r = mid;
        }
        //cerr << "best " << a << " " << bitset<G>(msk) << " : " << l << " " << fmsk(a, msk, l) << "\n";
        return l;
    };

    vector<ll> dp(1 << G, 1LL << 60);
    dp[0] = 0;
    for(int msk = 0; msk < (1 << G); msk++){
        //cerr << "dp " << bitset<G>(msk) << " : " << dp[msk] << "\n";
        for(int a = 0; a < G; a++){
            if(1 << a & msk) continue;
            int nxt = msk | (1 << a);
            int b = best(a, msk);
            ll t = dp[msk] + fmsk(a, msk, b);
            dp[nxt] = min(dp[nxt], t);
            //cerr << "trans " << bitset<G>(msk) << " -> " << bitset<G>(nxt) << " " << t << "\n";
        }
    }

    ll ans = dp[(1 << G) - 1];
    if(ans % 2 == 0) cout << ans / 2 << "\n";
    else cout << ans / 2 << ".5\n";
    
    return 0;
}

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