oj.uz

Submission #647598

# Submission time Handle Problem Language Result Execution time Memory
647598 2022-10-03T09:24:19 Z Pety Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 18008 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;
}

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);
  int 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))) {
        double cur = INF;
        for (int k = 0; k <= poz[i].size(); k++) {
          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];
          cur = min(cur, aux);
        }
        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:44:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for (int k = 0; k < poz[i].size(); k++) {
      |                       ~~^~~~~~~~~~~~~~~
passes.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (k + 1 < poz[i].size())
      |             ~~~~~~^~~~~~~~~~~~~~~
passes.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int k = 0; k <= poz[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~

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 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 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 7 ms 5492 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 6 ms 6472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 6732 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 6732 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 340 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 340 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 0 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 340 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 340 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 0 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 0 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 14 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 13 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 57 ms 1748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 52 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 56 ms 1792 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 54 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 53 ms 1736 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 52 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 52 ms 1728 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 52 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 56 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 51 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
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 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 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 7 ms 5492 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 6 ms 6472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 6732 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 6732 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 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 340 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 0 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 0 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 14 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 13 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 57 ms 1748 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 52 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 56 ms 1792 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 54 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 53 ms 1736 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 52 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 52 ms 1728 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 52 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 56 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 51 ms 1748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 29 ms 660 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 31 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 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 464 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 5 ms 5576 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 6 ms 6480 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 7 ms 6864 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 340 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 336 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 336 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 14 ms 1624 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 12 ms 1628 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 52 ms 1800 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 54 ms 1748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 55 ms 1748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 52 ms 1748 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 53 ms 1760 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 52 ms 1748 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 52 ms 1748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 51 ms 1748 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 51 ms 1748 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 53 ms 1756 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2082 ms 18008 KB Time limit exceeded
97 Halted 0 ms 0 KB -