oj.uz

Submission #647596

# Submission time Handle Problem Language Result Execution time Memory
647596 2022-10-03T09:23:23 Z Pety Boarding Passes (BOI22_passes) C++14
60 / 100
 54 ms 4840 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[12][100002];
vector<int>poz[10];
vector<double>calc[10][10];
double dp[(1 << 10)];

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 < 10; 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 < 10; 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 0 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 4 ms 3912 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4552 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4840 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4812 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 336 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 1 ms 324 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 336 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 1 ms 324 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 344 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 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 12 ms 1364 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 12 ms 1364 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 51 ms 1492 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 53 ms 1544 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 54 ms 1604 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 52 ms 1540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 54 ms 1492 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 54 ms 1500 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 52 ms 1540 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 51 ms 1532 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 51 ms 1492 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 53 ms 1492 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
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 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 4 ms 3912 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4552 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4840 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4812 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 336 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 1 ms 324 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 344 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 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 12 ms 1364 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 12 ms 1364 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 51 ms 1492 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 53 ms 1544 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 54 ms 1604 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 52 ms 1540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 54 ms 1492 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 54 ms 1500 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 52 ms 1540 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 51 ms 1532 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 51 ms 1492 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 53 ms 1492 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Runtime error 1 ms 468 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -