oj.uz

답안 #701896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701896 2023-02-22T09:56:37 Z Johann Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 1236 KB 
#include "bits/stdc++.h"
using namespace std;

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

vi B;
vd dp;

double calc(ll k1, ll k2)
{
    return (k1 * (k1 - 1) + k2 * (k2 - 1)) / (double)4;
}
double expectOneGroup(ll N)
{
    ll k1 = ceil(N / (double)2), k2 = floor(N / (double)2);
    return calc(k1, k2);
}
double 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 += o2;
        else if (B[i] & mask)
            ++o2;

    double res = dp[others] + safeOtherCost + calc(k1, k2);
    for (int i = 0; i < sz(B); ++i)
    {
        if (B[i] == lg)
        {
            ++k1, --k2;
            safeOtherCost = safeOtherCost - o2 + 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]);
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 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 1 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 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 320 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 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 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 1 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 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 320 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 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 316 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 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 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 320 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 320 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 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 32 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 23 ms 340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 325 ms 368 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 116 ms 340 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 123 ms 372 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 115 ms 380 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 130 ms 372 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 131 ms 372 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 130 ms 368 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 130 ms 372 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 129 ms 376 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 129 ms 340 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 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 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 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 1 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 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 320 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 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 288 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 316 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 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 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 320 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 320 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 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 32 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 23 ms 340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 325 ms 368 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 116 ms 340 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 123 ms 372 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 115 ms 380 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 130 ms 372 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 131 ms 372 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 130 ms 368 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 130 ms 372 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 129 ms 376 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 129 ms 340 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 11 ms 572 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 36 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 1 ms 788 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 1 ms 980 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 1 ms 980 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 1 ms 980 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 1 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 324 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 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 1 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 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 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 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 23 ms 340 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 23 ms 372 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 326 ms 368 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 114 ms 368 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 115 ms 340 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 123 ms 340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 132 ms 368 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 140 ms 340 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 130 ms 376 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 133 ms 372 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 133 ms 340 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 128 ms 368 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2073 ms 1236 KB Time limit exceeded
97 Halted 0 ms 0 KB -