Submission #576705

#	Time	Username	Problem	Language	Result	Execution time	Memory
576705		InternetPerson10	Boarding Passes (BOI22_passes)	C++17	60 / 100	2044 ms	15956 KiB

passes

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

using namespace std;

ll BIG = 1e13;

vector<int> nums;
vector<vector<int>> ct;
vector<ll> dp;
vector<vector<ll>> pref;
vector<vector<int>> v;

int n, g;

ll solve(int bit);

ll solvebit(int bit, int las) {
    int bi = bit - (1 << las);
    ll ans = solve(bi);
    ll tot = BIG, tot2 = 0;
    ll m = ct[las].size();
    if(m == 0) return ans;
    ll x = 0;
    for(int g : ct[las]) {
        for(int k : v[bi]) {
            tot2 += pref[k][g];
        }
    }
    for(int k : v[bi]) {
        x += pref[k][n];
    }
    tot = min(tot, 2 * tot2 + (m * m - m) / 2);
    for(ll i = m-1; i >= 0; i--) {
        tot2 += x;
        for(int k : v[bi]) {
            tot2 -= 2 * pref[k][ct[las][i]];
        }
        assert(tot2 >= 0);
        tot = min(tot, 2 * tot2 + (i * i - i) / 2 + ((m-i) * (m-i) - (m-i)) / 2);
    }
    return ans + tot;
}

ll solve(int bit) {
    if(bit == 0) return 0;
    if(dp[bit] != BIG) return dp[bit];
    ll ans = BIG;
    for(int i : v[bit]) {
        ans = min(ans, solvebit(bit, i));
    }
    return dp[bit] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    n = s.size();
    nums.resize(n);
    ct.resize(15);
    g = 0;
    for(int i = 0; i < n; i++) {
        nums[i] = s.at(i) - 'A';
        g = max(g, nums[i]+1);
        ct[nums[i]].push_back(i);
    }
    v.resize(1 << g);
    for(int i = 0; i < (1 << g); i++) {
        for(int j = 0; j < g; j++) {
            if((1 << j) & i) v[i].push_back(j);
        }
    }
    pref.resize(g);
    dp.resize(1 << g, BIG);
    dp[0] = 0;
    for(int i = 0; i < g; i++) {
        pref[i].resize(n+1);
        for(int j = 0; j < n; j++) {
            pref[i][j+1] = pref[i][j];
            if(nums[j] == i) pref[i][j+1]++;
        }
    }
    ll a = solve((1 << g) - 1);
    cout << a/2;
    if(a%2) cout << ".5\n";
    else cout << '\n';
}

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