Submission #722940

#	Time	Username	Problem	Language	Result	Execution time	Memory
722940		dxz05	Boarding Passes (BOI22_passes)	C++17	60 / 100	2045 ms	2064 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 double) 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();

    int m1 = (n - 1) / 2;
    int m2 = m1 + 1;

    long double ans = 5e18;

    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 sum_l = 0;
            vector<int> diff;

            for (int i : pos[c]){
                int l = cnt[i];
                int r = cnt.back() - cnt[i];
                sum_l += l;
                diff.push_back(r - l);
            }

            sort(all(diff));

            long long cur = 5e18;
            for (int half = 0; half <= sz; half++){
                if (half > 0) sum_l += diff[half - 1];
                cur = min(cur, sum_l * 4 + exp_inv(half) + exp_inv(sz - half));
            }

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

    }

    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;
}

Compilation message (stderr)

passes.cpp: In function 'void solve()':
passes.cpp:35:9: warning: unused variable 'm2' [-Wunused-variable]
   35 |     int m2 = m1 + 1;
      |         ^~
passes.cpp:37:17: warning: unused variable 'ans' [-Wunused-variable]
   37 |     long double ans = 5e18;
      |                 ^~~

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