oj.uz

Submission #647601

# Submission time Handle Problem Language Result Execution time Memory
647601 2022-10-03T09:43:45 Z Pety Boarding Passes (BOI22_passes) C++14
100 / 100
 272 ms 18248 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const double INF = 1e12;
const int MOD = 1e9 + 7;

int n, g, sum[15][100002];
vector<int>poz[15];
vector<double>calc[15][15];
double dp[(1 << 15)];

string s;

double expected(double n) {
  if (n < 2)
    return 0.0;
  return (double)n * (n - 1) / 4;
}

double func (int i, int mask, int k) {
  if (poz[i].size() - 1 - k < 0)
    return INF;
  double aux = expected(k) + expected(poz[i].size() - 1 - k);
  for (int j = 0; j < g; j++)
    if (mask & (1 << j))
      aux += calc[i][j][k];
  return aux;
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> s;
  int n = s.size();
  s = '#' + s;
  for (int i = 0; i < 15; i++)
    poz[i].push_back(0);
  g = 0;
  for (int i = 1; i <= n; i++) {
    g = max(g, s[i] - 'A' + 1);
    poz[s[i] - 'A'].push_back(i);
    for (int j = 0; j < 15; j++)
      sum[j][i] = sum[j][i - 1] + (s[i] - 'A' == j);
  }
  for (int i = 0; i < g; i++) {
    for (int j = 0; j < g; j++) {
      if (i == j)
        continue;
      calc[i][j].resize(poz[i].size() + 1);
      ll pas = 0;
      for (int k = 0; k < poz[i].size(); k++) {
        calc[i][j][k] += pas;
        if (k + 1 < poz[i].size())
          pas += sum[j][poz[i][k + 1]];
      }
      pas = 0;
      for (int k = poz[i].size() - 1; k >= 0; k--) {
        calc[i][j][k] += pas;
        pas += sum[j][n] - sum[j][poz[i][k] - 1];
      }
    }
  }
  for (int mask = 0; mask < (1 << g); mask++)
    dp[mask] = INF;
  dp[0] = 0;
  for (int mask = 0; mask < (1 << g); mask++) {
    for (int i = 0; i < g; i++)
      if (!(mask & (1 << i))) {
        int st = 0, dr = poz[i].size() - 1;
        while (dr - st > 2) {
          int m1 = st + (dr - st) / 3, m2 = dr - (dr - st) / 3;
          double v1 = func(i, mask, m1), v2 = func(i, mask, m2);
          if (v1 > v2) 
            st = m1;
          else
            dr = m2;
        }
        double cur = min({func(i, mask, st), func(i, mask, st + 1), func(i, mask, st + 2)});
        dp[mask ^ (1 << i)] = min(dp[mask] + cur, dp[mask ^ (1 << i)]);
      }
  }
  cout << fixed << setprecision(7) << dp[(1 << g) - 1];
  return 0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |       for (int k = 0; k < poz[i].size(); k++) {
      |                       ~~^~~~~~~~~~~~~~~
passes.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (k + 1 < poz[i].size())
      |             ~~~~~~^~~~~~~~~~~~~~~

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 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 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 5 ms 5576 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 6472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 6860 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 6868 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 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 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 340 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 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 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 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 336 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 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 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 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 340 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 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 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 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 336 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 340 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 340 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 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 340 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 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 2 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 5 ms 1748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 5 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 3 ms 1748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 5 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 5 ms 1748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 5 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 5 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 5 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 7 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 5 ms 1748 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 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 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 5 ms 5576 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 6472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 6860 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 6868 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 340 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 340 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 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 340 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 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 336 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 340 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 340 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 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 340 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 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 2 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 2 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 5 ms 1748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 5 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 3 ms 1748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 5 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 5 ms 1748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 5 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 5 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 5 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 7 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 5 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 36 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 28 ms 596 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 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 292 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 7 ms 5584 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 6 ms 6472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 6 ms 6860 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 6 ms 6860 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 340 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 340 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 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 460 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 340 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 2 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 2 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 4 ms 1748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 6 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 2 ms 1756 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 5 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 5 ms 1748 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 6 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 5 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 5 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 5 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 5 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 232 ms 18112 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 28 ms 468 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 266 ms 18000 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 60 ms 18124 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 32 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 272 ms 18128 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 227 ms 18248 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 243 ms 18148 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 234 ms 18064 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 222 ms 18096 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 231 ms 18136 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 227 ms 18068 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 109 ms 17104 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 231 ms 18172 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'