Submission #674521

#	Time	Username	Problem	Language	Result	Execution time	Memory
674521		stanislavpolyn	Boarding Passes (BOI22_passes)	C++17	60 / 100	2097 ms	39104 KiB

passes

#include <bits/stdc++.h>
 
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
 
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
 
using namespace std;
 
mt19937_64 rng(228);
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
 
template <typename T>
bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T>
bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; }
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
 
const int N = 1e5 + 5;
 
string s;
ve<int> v[26];
 
ld dp[pw(16)];
int pref[N][16];
int suff[N][16];
ve<int> p;

ll P[N][16];
ll S[N][16];
int last[16];

ld get(int mask, int i, int x) {
    ll ans = 0;
    if (x > 0) {
        fr (cur, 0, 15) {
            if (mask & pw(cur)) {
                ans += P[v[i][x - 1]][p[cur]];
            }
        }
    }
    if (x < sz(v[i])) {
        fr (cur, 0, 15) {
            if (mask & pw(cur)) {
                ans += S[v[i][x]][p[cur]];
            }
        }
    }
    ld res = ans;
    res += ld(0.5) * (1LL * x * (x - 1) / 2);
    res += ld(0.5) * (1LL * (sz(v[i]) - x) * (sz(v[i]) - x - 1) / 2);

    return res;
}
 
ld calc(int mask, int i) {
    ld best = 1e18;

    fr (take, 0, sz(v[i])) {
        umn(best, get(mask, i, take));
    }

    return best;
}
 
int main() {
#ifdef LOCAL
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif
    cin >> s;
 
    fr (i, 0, sz(s) - 1) {
        v[s[i] - 'A'].pb(i);
    }
 
    fr (i, 0, sz(s) - 1) {
        pref[i][s[i] - 'A'] = 1;
        if (i > 0) {
            fr (j, 0, 15) {
                pref[i][j] += pref[i - 1][j];
            }
        }
    }
    rf (i, sz(s) - 1, 0) {
        suff[i][s[i] - 'A'] = 1;
        if (i + 1 < sz(s)) {
            fr (j, 0, 15) {
                suff[i][j] += suff[i + 1][j];
            }
        }
    }

    {
        fill(last, last + 16, -1);
        fr (i, 0, sz(s) - 1) {
            fr (j, 0, 15) {
                P[i][j] = pref[i][j];
            }
            if (last[s[i] - 'A'] != -1) {
                fr (j, 0, 15) {
                    P[i][j] += P[last[s[i] - 'A']][j];
                }
            }

            last[s[i] - 'A'] = i;
        }
        fill(last, last + 16, -1);
        rf (i, sz(s) - 1, 0) {
            fr (j, 0, 15) {
                S[i][j] = suff[i][j];
            }
            if (last[s[i] - 'A'] != -1) {
                fr (j, 0, 15) {
                    S[i][j] += S[last[s[i] - 'A']][j];
                }
            }

            last[s[i] - 'A'] = i;
        }
    }
 
 
    fr (i, 0, 25) {
        if (sz(v[i])) {
            p.pb(i);
        }
    }
 
    fr (mask, 0, pw(sz(p)) - 1) {
        dp[mask] = 1e18;
    }
    dp[0] = 0;
 
    fr (mask, 0, pw(sz(p)) - 1) {
        fr (i, 0, sz(p) - 1) {
            if (!(mask & pw(i))) {
                umn(dp[mask | pw(i)], dp[mask] + calc(mask, p[i]));
            }
        }
    }
    cout << fixed << setprecision(10) << dp[pw(sz(p)) - 1] << "\n";

    return 0;
}

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