oj.uz

Submission #941892

# Submission time Handle Problem Language Result Execution time Memory
941892 2024-03-09T16:12:01 Z prairie2022 Boarding Passes (BOI22_passes) C++17
100 / 100
 151 ms 15196 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    const int G = 15;
    vector<int> seat[G];
    vector<ll> cross[G][G]; // [j][g] = j crosses g

    { // total crosses needed
        string s;
        cin >> s;
        int n = s.size();
        for(int i=0; i<n; i++) seat[s[i]-'A'].push_back(i+1);
        
        vector<int> pre(n+1);
        for(int g=0; g<G; g++){
            pre[0] = 0;
            for(int i=0; i<n; i++)
                pre[i+1] = pre[i]+(s[i]=='A'+g);
            for(int j=0; j<G; j++){
                auto &v = cross[j][g];
                v = {0};
                for(const int i : seat[j]) v.push_back(v.back()+pre[i]);
            }
            pre[n] = 0;
            for(int i=n-1; ~i; i--) pre[i] = pre[i+1]+(s[i]=='A'+g);
            for(int j=0; j<G; j++){
                auto &v  = cross[j][g];
                ll suf = 0;
                for(int i=(int)seat[j].size()-1; ~i; i--)
                    v[i] += (suf += pre[seat[j][i]-1]);
            }

            for(int j=0; j<G; j++){
                if(j==g){
                    for(auto &c: cross[j][g]) c -= seat[j].size();
                }
                else{
                    for(auto &c: cross[j][g]) c <<= 1;
                }
            }
        }
    }

    ll dp[1<<G];
    memset(dp, 0x3f, sizeof(dp));

    auto E = [&](int mask, int g)->ll{
        auto cost = [&](int i)->ll{
            ll ans = 0;
            for(int j=0; j<G; j++){
                if((mask>>j)&1) ans += cross[g][j][i];
            }
            return ans;
        };
        int l = 0, r = seat[g].size();
        while(l<r){
            int mid = (l+r)>>1;
            if(cost(mid+1)>cost(mid)) r = mid;
            else l = mid+1;
        }
        return cost(l);
    };
    dp[0] = 0;
    for(int mask = 1; mask<(1<<G); mask++){
        for(int g=0; g<G; g++){
            if((mask>>g)&1) dp[mask] = min(dp[mask], dp[mask^(1<<g)]+E(mask, g));
        }
    }
    ll ans = dp[(1<<G)-1];
    if(ans&1) cout << (ans>>1) << ".5\n";
    else cout << (ans>>1) << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 13 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 15 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 20 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 40 ms 11668 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 43 ms 13700 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 43 ms 14216 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 44 ms 14220 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 720 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 18 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 36 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 34 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 26 ms 736 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 24 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 32 ms 708 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 30 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 29 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 29 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 29 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 29 ms 700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 31 ms 856 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 30 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 34 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 30 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 30 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 720 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 18 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 36 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 34 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 26 ms 736 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 24 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 32 ms 708 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 30 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 29 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 29 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 29 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 29 ms 700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 31 ms 856 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 30 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 34 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 30 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 30 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 19 ms 708 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 18 ms 740 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 38 ms 736 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 34 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 26 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 24 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 32 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 28 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 29 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 29 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 29 ms 712 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 29 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 30 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 29 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 29 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 30 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 32 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 24 ms 2140 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 24 ms 2136 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 80 ms 2140 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 69 ms 1880 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 34 ms 2156 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 67 ms 1884 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 72 ms 2140 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 72 ms 2396 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 72 ms 2140 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 73 ms 2396 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 72 ms 2364 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 71 ms 2248 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 13 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 15 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 20 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 40 ms 11668 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 43 ms 13700 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 43 ms 14216 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 44 ms 14220 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 18 ms 720 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 18 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 36 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 34 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 26 ms 736 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 24 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 32 ms 708 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 30 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 29 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 29 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 29 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 29 ms 700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 31 ms 856 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 30 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 34 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 30 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 30 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 19 ms 708 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 18 ms 740 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 38 ms 736 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 34 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 26 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 24 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 32 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 28 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 29 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 29 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 29 ms 712 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 29 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 30 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 29 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 29 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 30 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 32 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 24 ms 2140 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 24 ms 2136 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 80 ms 2140 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 69 ms 1880 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 34 ms 2156 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 67 ms 1884 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 72 ms 2140 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 72 ms 2396 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 72 ms 2140 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 73 ms 2396 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 72 ms 2364 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 71 ms 2248 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 25 ms 972 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 36 ms 660 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 20 ms 600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 14 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 15 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 15 ms 720 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 20 ms 860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 40 ms 11668 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 43 ms 13456 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 48 ms 14128 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 45 ms 14228 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 18 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 18 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 37 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 34 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 26 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 24 ms 720 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 35 ms 600 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 29 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 30 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 29 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 29 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 29 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 30 ms 724 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 29 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 30 ms 708 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 30 ms 716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 30 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 23 ms 2140 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 24 ms 2176 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 73 ms 2244 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 70 ms 1884 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 34 ms 2136 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 67 ms 2016 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 74 ms 2396 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 71 ms 2456 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 72 ms 2336 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 71 ms 2392 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 73 ms 2140 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 73 ms 2396 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 150 ms 14424 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 41 ms 700 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 129 ms 14428 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 56 ms 14228 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 29 ms 600 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 127 ms 14408 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 142 ms 14684 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 135 ms 14708 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 132 ms 14680 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 151 ms 14788 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 143 ms 14672 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 131 ms 14684 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 126 ms 14428 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 136 ms 15196 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'