oj.uz

Submission #787391

# Submission time Handle Problem Language Result Execution time Memory
787391 2023-07-19T06:45:49 Z erray Boarding Passes (BOI22_passes) C++17
0 / 100
 1 ms 324 KB 
// 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(2) << (long double) 0.5 * ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB 1st numbers differ - expected: '100800.5000000000', found: '100000.0000000000', error = '0.0079414289'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Incorrect 1 ms 212 KB 1st numbers differ - expected: '1225.0000000000', found: '1200.0000000000', error = '0.0204081633'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Incorrect 1 ms 212 KB 1st numbers differ - expected: '1225.0000000000', found: '1200.0000000000', error = '0.0204081633'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB 1st numbers differ - expected: '100800.5000000000', found: '100000.0000000000', error = '0.0079414289'
2 Halted 0 ms 0 KB -