oj.uz

Submission #654424

# Submission time Handle Problem Language Result Execution time Memory
654424 2022-10-31T09:30:34 Z prvocislo Boarding Passes (BOI22_passes) C++17
100 / 100
 316 ms 17764 KB 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int g = 15;
vector<int> v[g];
vector<ll> dp((1 << g), 1e18);
vector<ll> pf[g][g]; // pf[i][j][l] = kolko pismen typu j musi prvych l pismen typu i predbehnut
ll c2(ll k)
{
    return k * (k - 1) / 2;
}
void upd(ll& a, ll b)
{
    a = min(a, b);
}
ll eval(int m, int i, int l) // maska, pismeno, kolko ide dolava
{
    ll ans = c2(l) + c2(v[i].size() - l);
    for (int j = 0; j < g; j++) if (m & (1 << j))
    {
        ll fr = pf[i][j][l] * 2ll;
        ll sub = pf[i][j][v[i].size()] - pf[i][j][l];
        ll bk = ((v[i].size() - l) * 1ll * ((ll)v[j].size()) - sub) * 2ll;
        ans += fr + bk;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    for (int a = 0; a < g; a++) for (int b = 0; b < g; b++) pf[a][b].push_back(0ll);
    for (int i = 0; i < s.size(); i++)
    {
        int a = s[i] - 'A'; 
        for (int b = 0; b < g; b++)
        {
            pf[a][b].push_back(pf[a][b].back() + (ll)v[b].size());
        }
        v[a].push_back(i);
    }
    dp[0] = 0;
    for (int m = 0; m < (1 << g); m++)
    {
        for (int i = 0; i < g; i++) if (!(m & (1 << i)))
        {
            int lo = 0, hi = v[i].size();
            while (hi - lo >= 5)
            {
                int m1 = (lo * 2 + hi) / 3, m2 = (lo + hi * 2) / 3;
                if (eval(m, i, m1) < eval(m, i, m2)) hi = m2;
                else lo = m1;
            }
            ll plus = 1e18;
            for (int mi = lo; mi <= hi; mi++) upd(plus, eval(m, i, mi));
            upd(dp[m | (1 << i)], dp[m] + plus);
        }
    }
    cout << dp[(1 << g) - 1] / 2;
    if (dp[(1 << g) - 1] & 1ll) cout << ".5\n";
    else cout << "\n";
    return 0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 724 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 14 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 16 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 29 ms 724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 53 ms 10664 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 53 ms 12584 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 56 ms 13352 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 55 ms 13352 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 26 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 53 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 49 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 28 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 25 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 60 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 29 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 29 ms 572 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 30 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 29 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 30 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 30 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 30 ms 724 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 32 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 30 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 28 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 26 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 53 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 49 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 28 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 25 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 60 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 29 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 29 ms 572 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 30 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 29 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 30 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 30 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 30 ms 724 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 32 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 30 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 28 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 19 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 24 ms 600 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 50 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 55 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 30 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 23 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 51 ms 616 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 29 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 29 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 28 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 32 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 30 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 28 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 31 ms 608 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 28 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 30 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 28 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 36 ms 2352 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 35 ms 2260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 159 ms 2260 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 172 ms 1888 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 43 ms 2360 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 152 ms 1876 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 147 ms 2516 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 149 ms 2260 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 163 ms 2260 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 145 ms 2260 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 183 ms 2388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 148 ms 2388 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 724 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 14 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 16 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 29 ms 724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 53 ms 10664 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 53 ms 12584 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 56 ms 13352 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 55 ms 13352 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 17 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 26 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 53 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 49 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 28 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 25 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 60 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 29 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 29 ms 572 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 30 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 29 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 30 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 30 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 30 ms 724 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 32 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 30 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 28 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 19 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 24 ms 600 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 50 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 55 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 30 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 23 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 51 ms 616 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 29 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 29 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 28 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 32 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 30 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 28 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 31 ms 608 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 28 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 30 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 28 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 36 ms 2352 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 35 ms 2260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 159 ms 2260 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 172 ms 1888 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 43 ms 2360 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 152 ms 1876 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 147 ms 2516 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 149 ms 2260 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 163 ms 2260 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 145 ms 2260 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 183 ms 2388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 148 ms 2388 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 23 ms 600 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 27 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 27 ms 760 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 14 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 16 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 19 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 30 ms 724 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 55 ms 10664 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 55 ms 12584 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 56 ms 13352 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 56 ms 13252 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 17 ms 596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 24 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 53 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 49 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 29 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 20 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 51 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 31 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 29 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 28 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 29 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 31 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 31 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 27 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 30 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 30 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 28 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 36 ms 2260 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 35 ms 2260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 149 ms 2260 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 154 ms 1880 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 40 ms 2380 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 149 ms 1876 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 147 ms 2532 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 147 ms 2380 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 155 ms 2260 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 149 ms 2260 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 152 ms 2388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 151 ms 2392 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 297 ms 15444 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 35 ms 596 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 276 ms 14960 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 67 ms 13352 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 25 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 296 ms 15168 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 316 ms 15840 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 288 ms 16084 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 306 ms 16916 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 291 ms 16260 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 295 ms 16116 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 298 ms 16180 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 290 ms 15820 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 287 ms 17764 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'