Submission #787392

#	Time	Username	Problem	Language	Result	Execution time	Memory
787392		erray	Boarding Passes (BOI22_passes)	C++17	100 / 100	684 ms	195828 KiB

passes

// author: erray
#undef DEBUG 
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string S;
  cin >> S;
  int N = int(S.size());
  int G = (*max_element(S.begin(), S.end())) - 'A' + 1;
  vector<vector<int>> pref(G, vector<int>(N + 1));
  vector<vector<int>> occ(G);            
  vector<vector<vector<long long>>> contrib(G, vector<vector<long long>>(G, vector<long long>(N + 1)));
  for (int l = 0; l < G; ++l) {
    for (int i = 0; i < N; ++i) {
      bool me = S[i] == ('A' + l);
      if (me) {
        occ[l].push_back(i);
      }
      pref[l][i + 1] = pref[l][i] + me;      
    }
  }
  for (int l = 0; l < G; ++l) {
    for (int i = 0; i < N; ++i) {
      bool me = S[i] == ('A' + l);      
      for (int j = 0; j < G; ++j) {
        contrib[j][l][i + 1] = contrib[j][l][i];
        if (me) {
          contrib[j][l][i + 1] += pref[j][i];
        }
      }
    }
  }
  debug(pref, contrib);
  auto Sq = [&](int x) {
    return 1LL * x * (x - 1) / 2;
  };
  vector<long long> best(1 << G, 1LL * N * N);
  best[0] = 0;
  vector<int> lg(1 << G);
  for (int m = 0; m < (1 << G); ++m) {
    if (m > 0) { lg[m] = __lg(m); }
    for (int i = 0; i < G; ++i) {
      if ((m >> i) % 2 == 0) {
        auto E = [&](int s) {
          int x = 0;
          if (s > 0) {
            x = occ[i][s - 1] + 1;
          }
          int cm = m;
          long long res = 0;
          while (cm > 0) {
            int l = lg[cm];
            debug(l, i);
            long long add = 2 * (contrib[l][i][x] + (contrib[i][l][N] - contrib[i][l][x] - 1LL * s * (pref[l][N] - pref[l][x]))); 
            assert(add >= 0);
            res += add;
            cm ^= 1 << l;
          } 
          res += Sq(s) + Sq(pref[i][N] - s);
          return res;
        };
        int low = 0, high = int(occ[i].size());
        while (low < high) {
          int mid = (low + high) >> 1;
          debug(mid, E(mid), E(mid + 1));
          if (E(mid) > E(mid + 1)) {
            low = mid + 1;
          } else {
            high = mid;
          }
        }
        debug(m, i, low, E(low));
        int next = m | (1 << i);
        best[next] = min(best[next], best[m] + E(low));   
      }
    }
  }
  long long ans = best[(1 << G) - 1];
  cout << setprecision(20) << (long double) 0.5 * ans << '\n';
}

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