oj.uz

Submission #894242

# Submission time Handle Problem Language Result Execution time Memory
894242 2023-12-28T03:05:52 Z box Boarding Passes (BOI22_passes) C++17
100 / 100
 233 ms 25560 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 16 ms 23128 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 10 ms 23288 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 10 ms 23128 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 12 ms 23132 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 22 ms 23132 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 27 ms 24980 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 28 ms 25168 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 31 ms 25448 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 41 ms 25212 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23132 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 23168 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 46 ms 23208 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 60 ms 23116 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 38 ms 23192 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 27 ms 23204 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 36 ms 23200 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 34 ms 23132 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 36 ms 23232 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 33 ms 23128 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 33 ms 23128 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 46 ms 23236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 47 ms 23132 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 36 ms 23128 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 44 ms 23132 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 35 ms 23132 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 35 ms 23132 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23132 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 23168 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 46 ms 23208 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 60 ms 23116 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 38 ms 23192 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 27 ms 23204 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 36 ms 23200 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 34 ms 23132 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 36 ms 23232 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 33 ms 23128 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 33 ms 23128 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 46 ms 23236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 47 ms 23132 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 36 ms 23128 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 44 ms 23132 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 35 ms 23132 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 35 ms 23132 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 14 ms 23324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 13 ms 23180 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 40 ms 23128 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 44 ms 23212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 30 ms 23132 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 34 ms 23104 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 36 ms 23168 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 43 ms 23132 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 38 ms 23132 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 33 ms 23128 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 33 ms 23104 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 33 ms 23128 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 35 ms 23236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 37 ms 23272 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 35 ms 23240 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 38 ms 23400 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 35 ms 23292 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 21 ms 23488 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 20 ms 23388 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 108 ms 23460 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 111 ms 23604 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 55 ms 23540 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 98 ms 23340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 100 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 106 ms 23364 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 107 ms 23324 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 102 ms 23384 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 160 ms 23436 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 101 ms 23376 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23128 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 10 ms 23288 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 10 ms 23128 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 12 ms 23132 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 22 ms 23132 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 27 ms 24980 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 28 ms 25168 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 31 ms 25448 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 41 ms 25212 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 19 ms 23132 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 13 ms 23168 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 46 ms 23208 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 60 ms 23116 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 38 ms 23192 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 27 ms 23204 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 36 ms 23200 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 34 ms 23132 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 36 ms 23232 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 33 ms 23128 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 33 ms 23128 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 46 ms 23236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 47 ms 23132 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 36 ms 23128 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 44 ms 23132 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 35 ms 23132 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 35 ms 23132 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 14 ms 23324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 13 ms 23180 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 40 ms 23128 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 44 ms 23212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 30 ms 23132 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 34 ms 23104 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 36 ms 23168 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 43 ms 23132 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 38 ms 23132 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 33 ms 23128 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 33 ms 23104 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 33 ms 23128 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 35 ms 23236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 37 ms 23272 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 35 ms 23240 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 38 ms 23400 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 35 ms 23292 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 21 ms 23488 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 20 ms 23388 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 108 ms 23460 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 111 ms 23604 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 55 ms 23540 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 98 ms 23340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 100 ms 23388 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 106 ms 23364 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 107 ms 23324 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 102 ms 23384 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 160 ms 23436 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 101 ms 23376 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 36 ms 23088 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 74 ms 23216 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 17 ms 23304 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 8 ms 23132 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 13 ms 23132 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 10 ms 23252 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 15 ms 23132 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 31 ms 24828 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 39 ms 25220 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 29 ms 25216 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 30 ms 25368 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 14 ms 23140 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 12 ms 23280 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 43 ms 23156 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 44 ms 23268 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 32 ms 23228 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 27 ms 23256 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 50 ms 23132 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 35 ms 23164 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 43 ms 23244 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 33 ms 23132 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 34 ms 23080 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 45 ms 23160 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 43 ms 23204 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 47 ms 23124 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 46 ms 23264 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 35 ms 23132 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 48 ms 23144 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 28 ms 23424 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 19 ms 23412 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 103 ms 23352 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 110 ms 23376 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 46 ms 23776 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 105 ms 23400 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 111 ms 23324 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 100 ms 23520 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 120 ms 23488 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 107 ms 23460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 113 ms 23452 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 100 ms 23380 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 211 ms 25560 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 71 ms 23132 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 218 ms 25212 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 67 ms 25356 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 52 ms 23080 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 208 ms 25268 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 233 ms 25168 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 228 ms 25168 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 214 ms 25120 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 233 ms 25224 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 207 ms 25180 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 212 ms 25368 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 210 ms 25260 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 217 ms 25412 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'