oj.uz

Submission #654358

# Submission time Handle Problem Language Result Execution time Memory
654358 2022-10-31T07:41:40 Z AlperenT Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 3308 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, G = 15;

int n, g;

double dp[1 << G], pans[N], lft[N], rght[N];

bool vis[N];

string str;

map<char, char> cmprs; 

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    for(int i = 2; i < N; i++) pans[i] = pans[i - 1] + (i - 1) / 2.0;

    for(int i = 0; i < (1 << G); i++) dp[i] = DBL_MAX;
    dp[0] = 0;

    cin >> str;

    n = str.size();

    for(auto c : str) cmprs[c] = '.';

    g = 0;

    for(auto &p : cmprs) p.second = 'A' + (++g - 1);

    for(auto &c : str) c = cmprs[c];

    for(int m = 0; m < (1 << g); m++){
        for(int cur = 0; cur < g; cur++){
            if(m & (1 << cur)) continue;
            else{
                memset(vis, 0, sizeof(vis));

                for(int i = 0; i < n; i++) if(m & (1 << (str[i] - 'A'))) vis[i] = true;

                int totalcnt = count(str.begin(), str.end(), 'A' + cur);

                int curcnt = 0, ptr = 0;

                for(int i = 1; i <= totalcnt; i++){
                    while(str[ptr] != 'A' + cur){
                        if(vis[ptr]) curcnt++;

                        ptr++;
                    }

                    lft[i] = lft[i - 1] + curcnt;

                    ptr++;
                }

                curcnt = 0, ptr = n - 1;

                for(int i = 1; i <= totalcnt; i++){
                    while(str[ptr] != 'A' + cur){
                        if(vis[ptr]) curcnt++;

                        ptr--;
                    }

                    rght[i] = rght[i - 1] + curcnt;

                    ptr--;
                }

                for(int i = 1; i <= totalcnt; i++){
                    lft[i] += pans[i];
                    rght[i] += pans[i];
                }

                for(int i = 0; i <= totalcnt; i++){
                    dp[m | (1 << cur)] = min(dp[m | (1 << cur)], dp[m] + lft[i] + rght[totalcnt - i]);
                }
            }
        }
    }

    cout << fixed << dp[(1 << g) - 1];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 2 ms 1372 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 2 ms 1492 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 1368 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 1364 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2916 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3156 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 3308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 3284 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 3 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 1368 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 1492 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 1364 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 1376 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 2 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 3 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 3 ms 1368 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 1492 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 1364 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 1376 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 2 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 2 ms 1364 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 1372 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 3 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 3 ms 1376 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 3 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 3 ms 1368 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 1468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 1364 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 3 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 3 ms 1376 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 2 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 3 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 3 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 3 ms 1340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 3 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 3 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 3 ms 1372 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 2 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 446 ms 1624 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 197 ms 1508 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 173 ms 1644 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 190 ms 1492 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 305 ms 1504 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 294 ms 1504 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 307 ms 1516 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 289 ms 1500 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 290 ms 1500 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 287 ms 1508 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 2 ms 1372 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 2 ms 1492 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 1368 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 1364 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 2916 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3156 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 3308 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 3284 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 2 ms 1368 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 3 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 3 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 3 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 3 ms 1368 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 4 ms 1492 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 3 ms 1364 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 2 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 3 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 3 ms 1376 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 3 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 2 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 3 ms 1364 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 3 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 3 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 3 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 2 ms 1364 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 1372 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 3 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 3 ms 1376 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 3 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 3 ms 1368 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 2 ms 1468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 2 ms 1364 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 3 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 3 ms 1376 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 2 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 3 ms 1364 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 3 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 3 ms 1340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 3 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 3 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 3 ms 1372 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 2 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 2 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 446 ms 1624 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 197 ms 1508 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 173 ms 1644 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 190 ms 1492 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 305 ms 1504 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 294 ms 1504 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 307 ms 1516 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 289 ms 1500 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 290 ms 1500 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 287 ms 1508 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 2 ms 1376 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 576 ms 1456 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 2 ms 1364 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 2 ms 1368 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 2 ms 1364 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 2 ms 1368 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 2 ms 1368 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 2924 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 5 ms 3172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 3300 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 3300 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 2 ms 1372 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 2 ms 1372 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 3 ms 1364 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 4 ms 1364 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 3 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 3 ms 1364 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 3 ms 1364 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 2 ms 1464 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 3 ms 1364 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 3 ms 1364 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 3 ms 1364 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 3 ms 1372 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 3 ms 1364 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 3 ms 1444 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 3 ms 1364 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 3 ms 1364 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 3 ms 1364 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 2 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 2 ms 1640 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 441 ms 1504 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 182 ms 1492 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 171 ms 1620 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 181 ms 1500 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 302 ms 1516 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 284 ms 1492 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 292 ms 1508 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 303 ms 1612 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 283 ms 1496 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 308 ms 1504 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2082 ms 1876 KB Time limit exceeded
97 Halted 0 ms 0 KB -