Submission #948765

#	Time	Username	Problem	Language	Result	Execution time	Memory
948765		ifateen	Boarding Passes (BOI22_passes)	C++17	60 / 100	2024 ms	4296 KiB

passes

#include <bits/stdc++.h>
using namespace std;
#define int long long
map<char, int> m;
long double dp[1 << 20];
signed main() {
    string s;
    cin >> s;
    vector<int> v(s.length());
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
        else v[i] = m[s[i]] = cnt++;
    }
    int G = *max_element(begin(v), end(v)) + 1;
    vector<vector<int>> pos(G);
    int n = s.length();
    for (int i = 0; i < n; ++i) pos[v[i]].push_back(i);
    dp[0] = 0;
    for (int mask = 1; mask < (1 << G); mask++) {
        dp[mask] = 1e18;
        for (int i = 0; i < G; i++) {
            if (!(mask & (1 << i))) continue;
            long double EV = 0;
            vector<long double> pref(n);
            pref[0] = (v[0] == i ? 0.5 : (mask & (1 << v[0])) ? 1.0 : 0.0);
            for (int j = 1; j < n; ++j) {
                pref[j] = pref[j - 1];
                if (v[j] == i) pref[j] += 0.5;
                else if (mask & (1 << v[j])) pref[j] += 1;
            }
            for (auto &j: pos[i]) {
                long double prev = j ? pref[j - 1] : 0, nd = pref[n - 1] - pref[j];
                EV += min(prev, nd);
            }
            dp[mask] = min(dp[mask], EV + dp[mask ^ (1 << i)]);
        }
    }
    cout << fixed << setprecision(8) << dp[(1 << G) - 1];
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:11:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < s.length(); ++i) {
      |                     ~~^~~~~~~~~~~~

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