Submission #1098955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098955		not_amir	Boarding Passes (BOI22_passes)	C++14	60 / 100	1253 ms	1404 KiB

passes

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

typedef long double ld;
typedef long long ll;

constexpr int N = 10;

int h[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    cin >> S;
    int n = S.size();
    for(char c : S) {
        h[c - 'A'] = 1;
    }
    for(int i = 0, it = 0; i < N; i++)
        if(h[i])
            h[i] = it++;
    ll res = n * n;
    vector<ll> dp(1 << N, ll(n) * ll(n));
    dp[0] = 0;
    for(int i = 1; i < 1 << N; i++) {
        for(int j = 0; j < N; j++) {
            if(i & (1 << j)) {
                ll ans = dp[i ^ (1 << j)];
                vector<ll> rem(n);
                for(int k = 0, it = 0, sum = 0; k < n; k++) {
                    if(h[S[k] - 'A'] == j) {
                        rem[k] = it++ + 2 * sum;
                        ans += rem[k];
                    }
                    else if(i & (1 << h[S[k] - 'A']))
                        sum++;
                }
                ll mini = ans;
                for(int k = n - 1, it = 0, sum = 0; k>= 0; k--) {
                    if(h[S[k] - 'A'] == j) {
                        ans -= rem[k];
                        ans += it++ + 2 * sum;
                    }
                    else if(i & (1 << h[S[k] - 'A']))
                        sum++;
                    mini = min(mini, ans);
                }
                dp[i] = min(dp[i], mini);
            }
        }
    }
    cout << fixed << setprecision(6) << ld(dp[(1 << N) - 1]) / 2.0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:25:8: warning: unused variable 'res' [-Wunused-variable]
   25 |     ll res = n * n;
      |        ^~~

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