oj.uz

Submission #636085

# Submission time Handle Problem Language Result Execution time Memory
636085 2022-08-28T00:19:36 Z null_awe Boarding Passes (BOI22_passes) C++14
100 / 100
 220 ms 41132 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n, g;
vector<vector<int>> p, pos;
vector<vector<ll>> l, r;

ll calc(int b, int s, int i) {
  ll ans = l[pos[b][i]][b] + r[pos[b][i + 1]][b];
  for (int bef = 0; bef < g; ++bef)
    if (s & (1 << bef)) ans += 2 * (l[pos[b][i]][bef] + r[pos[b][i + 1]][bef]);
  return ans;
}

int main() {
  string str; cin >> str;
  n = str.size(), g = 0;
  for (int i = 0; i < n; ++i) g = max(g, str[i] - 'A' + 1);
  p = vector<vector<int>>(n + 1, vector<int>(g));
  for (int i = 0; i < n; ++i) p[i + 1] = p[i], ++p[i + 1][str[i] - 'A'];
  l = vector<vector<ll>>(n, vector<ll>(g)), r = vector<vector<ll>>(n, vector<ll>(g));
  vector<vector<ll>> last(g, vector<ll>(g));
  for (int i = 0; i < n; ++i) {
    int val = str[i] - 'A';
    l[i] = last[val];
    for (int j = 0; j < g; ++j) l[i][j] += p[i][j];
    last[val] = l[i];
  }
  last = vector<vector<ll>>(g, vector<ll>(g));
  for (int i = n - 1; i >= 0; --i) {
    int val = str[i] - 'A';
    r[i] = last[val];
    for (int j = 0; j < g; ++j) r[i][j] += p[n][j] - p[i + 1][j];
    last[val] = r[i];
  }
  pos.resize(g);
  for (int i = 0; i < g; ++i) pos[i].push_back(0);
  for (int i = 0; i < n; ++i) pos[str[i] - 'A'].push_back(i);
  for (int i = 0; i < g; ++i) pos[i].push_back(n - 1);
  vector<ll> dp(1 << g, LLONG_MAX); dp[0] = 0;
  for (int mask = 1; mask < (1 << g); ++mask) {
    for (int b = 0; b < g; ++b) {
      if (!(mask & (1 << b))) continue;
      int bef = mask ^ (1 << b), lo = 0, hi = pos[b].size() - 1;
      while (lo < hi - 1) {
        int mid = (lo + hi) / 2;
        if (calc(b, bef, mid - 1) >= calc(b, bef, mid)) lo = mid;
        else hi = mid;
      }
      dp[mask] = min(dp[mask], dp[bef] + calc(b, bef, lo));
    }
  }
  ll ans = dp[(1 << g) - 1];
  cout << ans / 2;
  if (ans & 1) cout << ".5";
  cout << '\n';
  return 0;
}

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 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 21 ms 13992 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 22 ms 16516 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 24 ms 17488 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 27 ms 17528 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 0 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 304 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 0 ms 212 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 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 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 296 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 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 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 0 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 304 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 0 ms 212 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 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 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 296 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 300 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 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 296 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 296 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 300 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 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 300 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 212 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 1 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 3 ms 3156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 4 ms 3156 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 7 ms 3412 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 6 ms 3444 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 6 ms 3412 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 6 ms 3412 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 6 ms 3412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 6 ms 3412 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 6 ms 3412 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 7 ms 3412 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 6 ms 3412 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 6 ms 3412 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 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 21 ms 13992 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 22 ms 16516 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 24 ms 17488 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 27 ms 17528 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 304 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 0 ms 212 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 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 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 296 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 300 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 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 296 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 296 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 300 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 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 300 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 212 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 1 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 3 ms 3156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 4 ms 3156 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 7 ms 3412 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 6 ms 3444 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 6 ms 3412 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 6 ms 3412 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 6 ms 3412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 6 ms 3412 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 6 ms 3412 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 7 ms 3412 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 6 ms 3412 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 6 ms 3412 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 28 ms 468 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 54 ms 564 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 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 468 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 20 ms 13972 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 23 ms 16464 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 24 ms 17496 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 24 ms 17496 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 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 212 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 300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 0 ms 212 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 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 4 ms 3156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 3 ms 3124 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 6 ms 3412 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 6 ms 3412 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 5 ms 3412 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 6 ms 3412 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 6 ms 3412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 7 ms 3412 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 6 ms 3412 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 6 ms 3384 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 6 ms 3412 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 6 ms 3412 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 220 ms 41132 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 23 ms 460 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 196 ms 41084 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 87 ms 40960 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 38 ms 468 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 196 ms 41132 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 207 ms 41124 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 206 ms 41016 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 209 ms 41060 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 209 ms 41040 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 210 ms 40908 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 209 ms 40944 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 115 ms 39188 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 205 ms 41084 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'