Submission #954641

#	Time	Username	Problem	Language	Result	Execution time	Memory
954641		ifateen	Boarding Passes (BOI22_passes)	C++17	100 / 100	293 ms	169276 KiB

passes

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 5, MAXG = 15;
map<char, int> m;
vector<int> pos[MAXG];
int n, cnt = 0, G, v[MAXN], PREF[MAXG][MAXG][MAXN], SUF[MAXG][MAXG][MAXN], pref[MAXN][MAXG];
long double dp[1 << MAXG];
long double compute(int i, int count, int mask) {
    long double ret = 0;
    int rcnt = pos[i].size() - count;
    ret += count * (count - 1) * 0.25 + rcnt * (rcnt - 1) * 0.25;
    for (int j = 0; j < G; ++j)
        if (mask & (1 << j)) ret += (count ? PREF[i][j][count - 1] : 0) + (rcnt ? SUF[i][j][rcnt - 1] : 0);
    return ret;
}
signed main() {
    string s;
    cin >> s;
    n = s.length();
    for (int i = 0; i < n; ++i) {
        if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
        else v[i] = m[s[i]] = cnt++;
        G = max(G, v[i] + 1);
        pos[v[i]].push_back(i);
        pref[i][v[i]] = 1;
    }
    dp[0] = 0;
    for (int i = 1; i < n; ++i) for (int j = 0; j < G; ++j) pref[i][j] += pref[i - 1][j];
    for (int i = 0; i < G; ++i)
        for (int j = 0; j < G; ++j) {
            if (i == j) continue;
            for (int k = 0; k < pos[i].size(); ++k) {
                PREF[i][j][k] = pref[pos[i][k]][j] + (k ? PREF[i][j][k - 1] : 0);
            }
            for (int k = 0; k < pos[i].size(); ++k) {
                int idx = pos[i].size() - k - 1;
                SUF[i][j][k] = pref[n - 1][j] - (pos[i][idx] ? pref[pos[i][idx] - 1][j] : 0) + (k ? SUF[i][j][k - 1] : 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 = compute(i, pos[i].size(), mask), c;
            int l = 0, r = pos[i].size() - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if ((c = compute(i, mid, mask)) <= compute(i, mid + 1, mask)) EV = min(EV, c), r = mid - 1;
                else l = mid + 1;
            }
            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:33:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (int k = 0; k < pos[i].size(); ++k) {
      |                             ~~^~~~~~~~~~~~~~~
passes.cpp:36:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for (int k = 0; k < pos[i].size(); ++k) {
      |                             ~~^~~~~~~~~~~~~~~

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