Submission #723360

#	Time	Username	Problem	Language	Result	Execution time	Memory
723360		dxz05	Boarding Passes (BOI22_passes)	C++17	25 / 100	2070 ms	1172 KiB

passes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

long long exp_inv(ll n){
    return (long long) n * (n - 1); // should be divided by 4
}

ll dp[1 << 15];

void solve(){
    string s;
    cin >> s;
    int n = (int)s.size();

    vector<vector<int>> pos;
    map<char, int> id;

    for (int i = 0; i < n; i++){
        if (id.find(s[i]) == id.end()){
            id[s[i]] = (int) id.size();
            pos.emplace_back();
        }
        pos[id[s[i]]].push_back(i);
    }

    int G = (int) pos.size();

    fill(dp, dp + (1 << G), 5e18);

    dp[0] = 0;

    for (int mask = 0; mask < (1 << G); mask++){
        if (dp[mask] >= 1e18) continue;

        vector<int> cnt(n, 0);
        for (int c = 0; c < G; c++){
            if (mask & (1 << c)){
                for (int i : pos[c]) cnt[i] = 1;
            }
        }

        for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];

        for (int c = 0; c < G; c++){
            if (mask & (1 << c)) continue;

            int sz = (int) pos[c].size();

            long long mn = 5e18;
            for (int half = 0; half <= sz; half++){
                ll cur = 0;

                for (int i = 0; i < sz; i++){
                    int j = pos[c][i];
                    if (i < half){
                        cur += cnt[j];
                    } else {
                        cur += cnt.back() - cnt[j];
                    }
                }

                cur *= 4;
                cur += exp_inv(half) + exp_inv(sz - half);

                mn = min(mn, cur);
            }

            int new_mask = mask | (1 << c);
            dp[new_mask] = min(dp[new_mask], dp[mask] + mn);
        }

    }

    cout << fixed << setprecision(5);
    cout << (long double) dp[(1 << G) - 1] / 4 << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

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