Submission #598530

#	Time	Username	Problem	Language	Result	Execution time	Memory
598530		SuffixAutomata	Boarding Passes (BOI22_passes)	C++17	100 / 100	214 ms	10584 KiB

passes

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

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll
const int MOD = 1000000007;

ll wt[15][1 << 15];
ll dp[1 << 15];
int id[100005];
int con[100005][15];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  int S = 0;
  for (int i = 0; i < n; i++)
    S = max(S, id[i] = s[i] - 'A');
  S++;
  for (int i = 0; i < S; i++) {
    // todo: optimize this
    vector<int> pos;
    for (int j = 0; j < n; j++)
      if (id[j] == i)
        pos.push_back(j);
    ll cnt = pos.size();
    for (int k = 0; k <= cnt; k++)
      for (int j = 0; j < S; j++)
        con[k][j] = 0;
    int x = 0;
    for (int j = 0; j < n; j++) {
      if (x != cnt && j == pos[x]) {
        x++;
        continue;
      }
      con[x][id[j]]++;
    }
    for (int j = 0; j < S; j++) {
      int ds = 0, L = 0, R = 0;
      for (int k = 0; k <= cnt; k++)
        ds += k * con[k][j], R += con[k][j];
      for (int k = 0; k <= cnt; k++) {
        R -= con[k][j], L += con[k][j];
        con[k][j] = ds * 2;
        ds += L - R;
      }
    }
    for (int m = 0; m < (1 << S); m++) {
      if (m & (1 << i))
        continue;
      ll ans = 1e18;
      auto qry = [&](ll j) {
        if (j > cnt)
          return 1ll << 60;
        ll tmp = (j * (j - 1) + (cnt - j) * (cnt - j - 1)) / 2;
        for (int k = 0; k < S; k++)
          if (m & (1 << k))
            tmp += con[j][k];
        ans = min(ans, tmp);
        return tmp;
      };
      ll lo = 0, hi = cnt;
      while (lo <= hi) {
        ll mi = (lo + hi) / 2;
        if (qry(mi) <= qry(mi + 1))
          hi = mi - 1;
        else
          lo = mi + 1;
      }
      wt[i][m] = ans;
    }
  }
  dp[0] = 0;
  for (int i = 1; i < (1 << S); i++) {
    dp[i] = 1e18;
    for (int j = 0; j < S; j++)
      if (i & (1 << j))
        dp[i] = min(dp[i], dp[i ^ (1 << j)] + wt[j][i ^ (1 << j)]);
  }
  cout << dp[(1 << S) - 1] / 2;
  if (dp[(1 << S) - 1] % 2)
    cout << ".5";
  cout << endl;
  return 0;
}

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