oj.uz

Submission #691968

# Submission time Handle Problem Language Result Execution time Memory
691968 2023-02-01T03:39:54 Z bdl Boarding Passes (BOI22_passes) C++17
100 / 100
 226 ms 25264 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 (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();
        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 11 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 6 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 684 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 11 ms 960 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 35 ms 20104 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 35 ms 23860 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 37 ms 25224 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 36 ms 25224 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 748 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 30 ms 764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 32 ms 668 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 19 ms 732 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 19 ms 648 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 26 ms 736 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 26 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 28 ms 704 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 23 ms 716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 24 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 736 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 25 ms 640 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 26 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 24 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 25 ms 724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 26 ms 640 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 748 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 30 ms 764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 32 ms 668 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 19 ms 732 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 19 ms 648 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 26 ms 736 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 26 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 28 ms 704 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 23 ms 716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 24 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 736 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 25 ms 640 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 26 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 24 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 25 ms 724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 26 ms 640 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 10 ms 712 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 8 ms 712 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 29 ms 732 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 31 ms 688 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 19 ms 724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 18 ms 708 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 26 ms 716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 24 ms 716 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 26 ms 684 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 23 ms 700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 24 ms 716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 24 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 25 ms 668 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 29 ms 712 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 25 ms 716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 26 ms 716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 28 ms 756 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 15 ms 3228 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 15 ms 3156 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 84 ms 3208 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 90 ms 3172 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 30 ms 3220 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 75 ms 3116 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 82 ms 3148 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 82 ms 3060 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 89 ms 3080 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 93 ms 3148 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 83 ms 3164 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 81 ms 3108 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 6 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 684 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 11 ms 960 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 35 ms 20104 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 35 ms 23860 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 37 ms 25224 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 36 ms 25224 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 9 ms 748 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 8 ms 700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 30 ms 764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 32 ms 668 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 19 ms 732 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 19 ms 648 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 26 ms 736 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 26 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 28 ms 704 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 23 ms 716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 24 ms 724 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 24 ms 736 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 25 ms 640 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 26 ms 684 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 24 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 25 ms 724 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 26 ms 640 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 10 ms 712 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 8 ms 712 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 29 ms 732 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 31 ms 688 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 19 ms 724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 18 ms 708 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 26 ms 716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 24 ms 716 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 26 ms 684 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 23 ms 700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 24 ms 716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 24 ms 676 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 25 ms 668 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 29 ms 712 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 25 ms 716 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 26 ms 716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 28 ms 756 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 15 ms 3228 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 15 ms 3156 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 84 ms 3208 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 90 ms 3172 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 30 ms 3220 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 75 ms 3116 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 82 ms 3148 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 82 ms 3060 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 89 ms 3080 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 93 ms 3148 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 83 ms 3164 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 81 ms 3108 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 19 ms 716 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 47 ms 652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 11 ms 908 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 5 ms 704 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 7 ms 716 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 7 ms 712 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 12 ms 980 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 30 ms 20100 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 37 ms 23876 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 37 ms 25200 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 36 ms 25224 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 9 ms 712 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 9 ms 724 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 30 ms 680 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 32 ms 640 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 21 ms 736 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 18 ms 724 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 25 ms 716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 24 ms 704 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 26 ms 692 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 23 ms 680 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 24 ms 712 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 25 ms 648 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 24 ms 716 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 26 ms 720 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 26 ms 700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 25 ms 648 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 27 ms 724 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 15 ms 3260 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 15 ms 3168 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 85 ms 3188 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 82 ms 3152 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 29 ms 3276 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 79 ms 3148 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 86 ms 3136 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 81 ms 3172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 83 ms 3148 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 82 ms 3096 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 94 ms 3112 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 87 ms 3148 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 187 ms 25104 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 46 ms 716 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 226 ms 25084 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 61 ms 25264 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 31 ms 716 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 175 ms 25132 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 188 ms 25152 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 190 ms 25208 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 180 ms 25168 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 191 ms 25172 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 185 ms 25220 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 187 ms 25244 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 174 ms 25172 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 182 ms 25200 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'