oj.uz

Submission #701900

# Submission time Handle Problem Language Result Execution time Memory
701900 2023-02-22T10:12:20 Z Johann Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 1108 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
#define sz(x) (int)(x).size()

vi B;
vl dp; // the results are only 1/2 away from integers, so i store 2 * res in the dp

ll calc(ll k1, ll k2)
{
    return (k1 * (k1 - 1) + k2 * (k2 - 1)) / 2;
}
double expectOneGroup(ll N)
{
    ll k1 = ceil(N / (double)2), k2 = floor(N / (double)2);
    return calc(k1, k2) / (double)2;
}
ll compute(int mask, int lg) // lg is a bitvector with the bit of the group set
{
    int others = mask ^ lg;
    ll k1 = 0, k2 = 0; // passenger split of this Gruop lg
    ll o1 = 0, o2 = 0; // other passengers l and right
    ll safeOtherCost = 0;

    for (int i = sz(B) - 1; i >= 0; --i)
        if (B[i] == lg)
            ++k2, safeOtherCost += 2 * o2;
        else if (B[i] & mask)
            ++o2;

    ll res = dp[others] + safeOtherCost + calc(k1, k2);
    for (int i = 0; i < sz(B); ++i)
    {
        if (B[i] == lg)
        {
            ++k1, --k2;
            safeOtherCost = safeOtherCost - 2 * o2 + 2 * o1;
        }
        else if (B[i] & mask)
        {
            ++o1, --o2;
        }
        res = min(res, dp[others] + safeOtherCost + calc(k1, k2));
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    string P;
    cin >> P;
    ll N = sz(P);
    int G = 0;
    B.resize(N);
    for (int i = 0; i < N; ++i)
        B[i] = (1 << (P[i] - 'A')), G = max(G, P[i] - 'A');
    ++G; // to get the size
    dp.assign(1 << G, calc(100100, 100100));
    dp[0] = 0;
    for (int i = 1; i < sz(dp); ++i)
    {
        for (int j = 0; j < G; ++j)
        { // last group to enter
            if (((1 << j) & i) == 0)
                continue;
            dp[i] = min(dp[i], compute(i, (1 << j)));
        }
    }
    // double res = expectOneGroup(N);
    printf("%f\n", dp[(1 << G) - 1] / (double)2);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 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 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 724 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 852 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 852 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 0 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 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 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 0 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 0 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 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 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 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 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 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 212 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 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 0 ms 212 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 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 212 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 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 29 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 28 ms 360 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 334 ms 360 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 133 ms 364 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 133 ms 360 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 132 ms 340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 146 ms 364 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 147 ms 340 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 145 ms 360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 146 ms 340 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 144 ms 356 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 146 ms 360 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 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 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 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 1 ms 724 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1 ms 852 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1 ms 852 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 0 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 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 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 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 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 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 212 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 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 0 ms 212 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 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 212 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 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 29 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 28 ms 360 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 334 ms 360 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 133 ms 364 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 133 ms 360 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 132 ms 340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 146 ms 364 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 147 ms 340 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 145 ms 360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 146 ms 340 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 144 ms 356 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 146 ms 360 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 12 ms 468 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 38 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 212 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 1 ms 724 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 1 ms 852 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 1 ms 852 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 1 ms 852 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 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 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 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 1 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 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 27 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 27 ms 380 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 331 ms 356 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 136 ms 460 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 134 ms 340 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 132 ms 356 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 146 ms 364 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 144 ms 360 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 145 ms 360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 146 ms 360 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 147 ms 364 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 147 ms 340 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2077 ms 1108 KB Time limit exceeded
97 Halted 0 ms 0 KB -