oj.uz

Submission #636084

# Submission time Handle Problem Language Result Execution time Memory
636084 2022-08-28T00:18:32 Z null_awe Boarding Passes (BOI22_passes) C++14
100 / 100
 239 ms 41260 KB 
#include <iostream>
#include <vector>
#include <climits>
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 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 304 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 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 18 ms 14032 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 24 ms 16552 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 24 ms 17580 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 25 ms 17456 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 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 212 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 300 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 300 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 300 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 1 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 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 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 212 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 300 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 300 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 300 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 1 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 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 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 300 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 300 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 296 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 300 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 300 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 0 ms 304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 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 1 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 3 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 3412 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 4 ms 3412 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 5 ms 3380 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 7 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 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 304 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 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 18 ms 14032 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 24 ms 16552 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 24 ms 17580 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 25 ms 17456 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 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 212 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 300 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 0 ms 300 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 300 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 1 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 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 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 300 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 300 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 296 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 300 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 300 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 0 ms 304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 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 1 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 3 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 3412 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 4 ms 3412 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 5 ms 3380 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 7 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 560 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 53 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 464 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 300 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 300 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 14004 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 25 ms 17488 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 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 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 300 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 0 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 0 ms 300 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 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 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 300 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 3 ms 3120 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 4 ms 3120 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 6 ms 3472 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 6 ms 3440 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 6 ms 3416 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 3376 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 239 ms 41232 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 24 ms 464 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 197 ms 41188 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 88 ms 41036 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 41 ms 564 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 196 ms 41260 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 205 ms 41244 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 234 ms 41060 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 211 ms 41240 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 208 ms 41068 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 206 ms 41004 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 210 ms 41152 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 120 ms 39280 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 206 ms 41108 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'