oj.uz

Submission #787386

# Submission time Handle Problem Language Result Execution time Memory
787386 2023-07-19T06:42:11 Z erray Boarding Passes (BOI22_passes) C++17
100 / 100
 851 ms 195836 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];
  bool odd = ans % 2;
  cout << ans / 2;
  if (odd) {
    cout << ".5";
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 316 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 2720 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 3172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 3392 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 0 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 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 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 212 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 0 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 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 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 0 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 0 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 0 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 0 ms 212 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 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 4 ms 6356 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 4 ms 6412 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 8 ms 9428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 9 ms 9428 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 6 ms 9428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 8 ms 9428 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 11 ms 9172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 8 ms 9172 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 7 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 9160 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 316 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 2720 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 3172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 3392 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 0 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 340 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 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 0 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 0 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 0 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 0 ms 212 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 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 4 ms 6356 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 4 ms 6412 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 8 ms 9428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 9 ms 9428 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 6 ms 9428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 8 ms 9428 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 11 ms 9172 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 8 ms 9172 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 7 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 9160 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 23 ms 768 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 43 ms 776 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 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 0 ms 340 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 2 ms 3172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 3392 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 3392 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 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 0 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 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 316 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 212 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 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 0 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 3 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 9428 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 9428 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 8 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 9160 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 9172 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 665 ms 195756 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 578 ms 195720 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 322 ms 195832 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 29 ms 724 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 582 ms 195836 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 637 ms 195756 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 602 ms 194832 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 650 ms 194860 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 851 ms 194752 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 650 ms 194756 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 630 ms 194832 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 401 ms 170944 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 663 ms 194860 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'