oj.uz

Submission #787392

# Submission time Handle Problem Language Result Execution time Memory
787392 2023-07-19T06:46:14 Z erray Boarding Passes (BOI22_passes) C++17
100 / 100
 684 ms 195828 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(20) << (long double) 0.5 * ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 316 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2720 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 3256 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 3276 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 316 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 316 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 316 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 328 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 320 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 288 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 316 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 316 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 316 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 328 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 320 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 288 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 316 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 320 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 4 ms 6340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 4 ms 6356 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 10 ms 9428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 12 ms 9544 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 8 ms 9428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 11 ms 9420 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 8 ms 9172 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 10 ms 9172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 9 ms 9172 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 8 ms 9172 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 8 ms 9172 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 8 ms 9172 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 316 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2720 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 3256 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 3276 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 320 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 316 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 316 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 316 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 328 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 320 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 288 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 316 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 320 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 4 ms 6340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 4 ms 6356 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 10 ms 9428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 12 ms 9544 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 8 ms 9428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 11 ms 9420 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 8 ms 9172 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 10 ms 9172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 9 ms 9172 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 8 ms 9172 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 8 ms 9172 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 8 ms 9172 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 22 ms 768 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 43 ms 724 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 316 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 2720 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 3172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 3276 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 3276 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 316 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 320 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 316 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 4 ms 6356 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 4 ms 6356 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 8 ms 9428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 8 ms 9416 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 6 ms 9428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 8 ms 9404 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 8 ms 9172 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 9 ms 9172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 8 ms 9172 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 8 ms 9156 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 8 ms 9172 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 8 ms 9156 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 679 ms 195776 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 20 ms 596 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 585 ms 195828 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 328 ms 195780 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 38 ms 756 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 616 ms 195780 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 637 ms 195724 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 684 ms 194756 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 623 ms 194756 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 645 ms 194856 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 610 ms 194744 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 634 ms 194652 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 386 ms 170820 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 622 ms 194692 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'