oj.uz

Submission #691953

# Submission time Handle Problem Language Result Execution time Memory
691953 2023-02-01T03:26:50 Z bdl Boarding Passes (BOI22_passes) C++17
5 / 100
 40 ms 25224 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;


const int N = 1e5, A = 15;

int p2(const int& i) {
  return 1 << i;
}

long long l[A][N], r[A][N];
vector<int> p[A];
int n;

long long c2(int k) {
  return 1LL * k * (k - 1) / 2;
}

long long cost(int i, int j, int k) {
  long long x = c2(k) + c2(p[j].size() - k);
  for (int u = 0; u < A; u++)
    if (i & p2(u)) {
      if (p[u].empty())
        continue;
      if (k > 0)
        x += 2 * l[u][p[j][k - 1]];
      if (k < (int) p[j].size())
        x += 2 * r[u][p[j][k]];
    }
  return x;
}

void print(long long x) {
  if (x % 2 == 0)
    cout << x / 2 << '\n';
  else
    cout << x / 2 << ".5" << '\n';
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  string s;
  cin >> s;
  n = s.size();
  for (int i = 0; i < n; i++)
    p[s[i] - 'A'].push_back(i);
  for (int i = 0; i < A; i++) {
    static int k[N];
    for (int j = 0; j < n; j++)
      k[j] = (s[j] - 'A' == i ? 1 : 0) + (j > 0 ? k[j - 1] : 0);
    for (int j = 0; j < A; j++) {
      int last = -1;
      for (int u : p[j])
        l[i][u] = k[u] + (last != -1 ? l[i][last] : 0), last = u;
      last = -1;
      reverse(p[j].begin(), p[j].end());
      for (int u : p[j])
        r[i][u] = (k[n - 1] - k[u]) + (last != -1 ? r[i][last] : 0), last = u;
      reverse(p[j].begin(), p[j].end());
    }
  }
  static long long f[1 << A];
  f[0] = 0;
  for (int i = 1; i < 1 << A; i++) {
    f[i] = 1e18;
    for (int j = 0; j < A; j++)
      if (i & p2(j)) {
        if (p[j].size() == 0) {
          f[i] = min(f[i], f[i ^ p2(j)]);
          continue;
        }
        int low = 0, hi = p[j].size() - 1;
        while (low < hi) {
          int m = (low + hi) / 2;
          if (cost(i ^ p2(j), j, m) < cost(i ^ p2(j), j, m + 1))
            hi = m;
          else
            low = m + 1;
        }
        f[i] = min(f[i], f[i ^ p2(j)] + cost(i ^ p2(j), j, low));
      }
  }
  print(f[(1 << A) - 1]);
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 852 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 3 ms 656 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 5 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 744 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 13 ms 892 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 32 ms 20104 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 39 ms 23900 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 40 ms 25224 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 37 ms 25224 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 708 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 11 ms 756 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 30 ms 716 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 33 ms 628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 13 ms 684 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 708 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 11 ms 756 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 30 ms 716 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 33 ms 628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Incorrect 13 ms 684 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 852 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 3 ms 656 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 5 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 744 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 13 ms 892 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 32 ms 20104 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 39 ms 23900 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 40 ms 25224 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 37 ms 25224 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 8 ms 708 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 11 ms 756 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 30 ms 716 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 33 ms 628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Incorrect 13 ms 684 KB 1st numbers differ - expected: '1087.0000000000', found: '1339.0000000000', error = '0.2318307268'
15 Halted 0 ms 0 KB -