Submission #858990

#	Time	Username	Problem	Language	Result	Execution time	Memory
858990		vgtcross	Boarding Passes (BOI22_passes)	C++17	25 / 100	2017 ms	3164 KiB

passes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100100;
const int K = 15;

ll p[N][K];
ll dp[1 << K];

void solve() {
    string s;
    cin >> s;
    
    int n = s.size();
    
    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = s[i] - 'A';
    
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int j = 1; j < (1 << K); ++j) {
        for (int i = 0; i < K; ++i) if (j >> i & 1) {
            ll l[2]{}, r[2]{}, t = 0;
            for (int k : v) {
                r[0] += k == i;
                if (i != k && (j >> k & 1)) {
                    ++r[1];
                    t += r[0];
                }
            }
            
            dp[j] = min(dp[j], dp[j ^ (1 << i)] + r[0]*(r[0]-1)/2 + 2*t);
            for (int k : v) {
                l[0] += k == i;
                r[0] -= k == i;
                l[1] += i != k && (j >> k & 1);
                r[1] -= i != k && (j >> k & 1);
                if (k == i) {
                    t -= r[1];
                    t += l[1];
                }
                
                dp[j] = min(dp[j], dp[j ^ (1 << i)] + l[0]*(l[0]-1)/2 + r[0]*(r[0]-1)/2 + 2*t);
            }
            //cout << bitset<3>(j) << ' ' << bitset<3>(1 << i) << ": " << dp[j] << '\n';
        }
    }
    
    cout << (long double) dp[(1 << K) - 1] / 2.0 << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cout << fixed << setprecision(6);
    
    solve();
}

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