Submission #574148

#	Time	Username	Problem	Language	Result	Execution time	Memory
574148		eecs	Boarding Passes (BOI22_passes)	C++17	100 / 100	272 ms	177416 KiB

passes

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

const int maxn = 100010, n = 15;
int cnt[n], pre[maxn][n][n], suf[maxn][n][n];
string str;
long long f[1 << n];
vector<int> pos[n];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> str;
    fill(pos, pos + n, vector<int>{-1});
    for (int i = 0; i < str.size(); i++) {
        pos[str[i] - 'A'].push_back(i);
        if (i) memcpy(pre[i], pre[i - 1], sizeof(pre[i]));
        for (int j = 0; j < n; j++) pre[i][str[i] - 'A'][j] += cnt[j];
        cnt[str[i] - 'A']++;
    }
    fill(cnt, cnt + n, 0);
    for (int i = str.size() - 1; ~i; i--) {
        memcpy(suf[i], suf[i + 1], sizeof(suf[i]));
        for (int j = 0; j < n; j++) suf[i][str[i] - 'A'][j] += cnt[j];
        cnt[str[i] - 'A']++;
    }
    fill(f + 1, f + (1 << n), 1e18);
    for (int S = 0; S < 1 << n; S++) {
        for (int i = 0; i < n; i++) if (!(S >> i & 1)) {
            auto calc = [&](int p) {
                int r = pos[i].size() - p - 1, T = S;
                long long s = (1LL * p * (p - 1) + 1LL * r * (r - 1)) / 2;
                p = pos[i][p];
                for (int T = S, j; T; T ^= 1 << j) {
                    j = __builtin_ctz(T);
                    if (~p) s += 2 * pre[p][i][j];
                    s += 2 * suf[p + 1][i][j];
                }
                return s;
            };
            int l = 1, r = pos[i].size() - 1, p = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                calc(mid) < calc(mid - 1) ? l = (p = mid) + 1 : r = mid - 1;
            }
            f[S | (1 << i)] = min(f[S | (1 << i)], f[S] + calc(p));
        }
    }
    cout << f[(1 << n) - 1] / 2 << (f[(1 << n) - 1] % 2 ? ".5" : "") << "\n";
    return 0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < str.size(); i++) {
      |                     ~~^~~~~~~~~~~~
passes.cpp: In lambda function:
passes.cpp:30:48: warning: unused variable 'T' [-Wunused-variable]
   30 |                 int r = pos[i].size() - p - 1, T = S;
      |                                                ^

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