oj.uz

Submission #807641

# Submission time Handle Problem Language Result Execution time Memory
807641 2023-08-04T20:59:52 Z dong_liu Boarding Passes (BOI22_passes) C++17
100 / 100
 235 ms 25332 KB 
#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 13 ms 948 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 6 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 8 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 7 ms 724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 13 ms 932 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 30 ms 20144 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 38 ms 23908 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 34 ms 25296 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 35 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 12 ms 740 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 10 ms 724 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 38 ms 676 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 40 ms 640 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 25 ms 724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 24 ms 652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 33 ms 732 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 32 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 688 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 31 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 31 ms 716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 31 ms 724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 33 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 34 ms 660 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 31 ms 664 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 33 ms 704 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 32 ms 728 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 740 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 10 ms 724 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 38 ms 676 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 40 ms 640 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 25 ms 724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 24 ms 652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 33 ms 732 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 32 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 688 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 31 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 31 ms 716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 31 ms 724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 33 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 34 ms 660 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 31 ms 664 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 33 ms 704 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 32 ms 728 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 12 ms 732 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 12 ms 668 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 39 ms 696 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 40 ms 704 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 26 ms 656 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 24 ms 688 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 33 ms 716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 31 ms 700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 35 ms 692 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 31 ms 640 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 31 ms 704 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 31 ms 700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 32 ms 620 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 34 ms 680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 31 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 33 ms 692 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 32 ms 704 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 17 ms 3152 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 17 ms 3236 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 104 ms 3152 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 102 ms 3136 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 40 ms 3156 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 92 ms 3144 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 99 ms 3152 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 102 ms 3152 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 99 ms 3152 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 99 ms 3136 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 101 ms 3152 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 105 ms 3252 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 948 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 6 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 8 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 7 ms 724 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 13 ms 932 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 30 ms 20144 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 38 ms 23908 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 34 ms 25296 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 35 ms 25224 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 12 ms 740 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 10 ms 724 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 38 ms 676 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 40 ms 640 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 25 ms 724 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 24 ms 652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 33 ms 732 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 32 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 39 ms 688 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 31 ms 684 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 31 ms 716 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 31 ms 724 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 33 ms 680 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 34 ms 660 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 31 ms 664 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 33 ms 704 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 32 ms 728 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 12 ms 732 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 12 ms 668 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 39 ms 696 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 40 ms 704 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 26 ms 656 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 24 ms 688 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 33 ms 716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 31 ms 700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 35 ms 692 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 31 ms 640 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 31 ms 704 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 31 ms 700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 32 ms 620 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 34 ms 680 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 31 ms 724 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 33 ms 692 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 32 ms 704 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 17 ms 3152 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 17 ms 3236 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 104 ms 3152 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 102 ms 3136 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 40 ms 3156 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 92 ms 3144 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 99 ms 3152 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 102 ms 3152 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 99 ms 3152 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 99 ms 3136 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 101 ms 3152 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 105 ms 3252 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 26 ms 716 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 71 ms 632 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 13 ms 852 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 6 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 9 ms 848 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 7 ms 848 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 21 ms 980 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 30 ms 20112 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 34 ms 23860 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 37 ms 25332 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 34 ms 25232 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 12 ms 632 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 10 ms 692 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 38 ms 716 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 40 ms 720 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 26 ms 716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 25 ms 740 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 34 ms 724 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 33 ms 688 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 35 ms 700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 31 ms 676 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 31 ms 736 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 31 ms 644 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 32 ms 728 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 34 ms 716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 32 ms 736 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 33 ms 732 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 32 ms 776 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 17 ms 3156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 17 ms 3228 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 102 ms 3120 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 103 ms 3148 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 40 ms 3192 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 101 ms 3256 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 100 ms 3120 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 107 ms 3064 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 108 ms 3132 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 100 ms 3160 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 105 ms 3364 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 99 ms 3160 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 221 ms 25140 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 67 ms 712 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 235 ms 25160 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 73 ms 25216 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 50 ms 736 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 191 ms 25096 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 209 ms 25316 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 211 ms 25240 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 208 ms 25216 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 214 ms 25148 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 214 ms 25164 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 207 ms 25176 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 198 ms 25152 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 211 ms 25284 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'