oj.uz

Submission #938533

# Submission time Handle Problem Language Result Execution time Memory
938533 2024-03-05T09:15:36 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 8272 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_G = 15;
const int MAX_N = 1e5;
int n, g;
string s;
double dp[1 << MAX_G];
int frecv[MAX_G][MAX_N + 1];
double costPref[MAX_N + 2], costSuf[MAX_N + 2];
unordered_map<char, int> lit;

double expectedInversions( int n ) {
    return (double)n * (n - 1) / 4;
}

double solve( int c, int mask ) {
    int crt, prv;

    crt = prv = 0;
    costPref[0] = 0;
    for ( int i = 1; i <= n; i++ ) {
        costPref[i] = costPref[i - 1];
        if ( s[i] == c ) {
            crt++;
            costPref[i] += prv;
        }
        if ( (mask >> s[i]) & 1 )
            prv++;
    }
    crt = prv = 0;
    costSuf[n + 1] = 0;
    for ( int i = n; i >= 1; i-- ) {
        costSuf[i] = costSuf[i + 1];
        if ( s[i] == c ) {
            crt++;
            costSuf[i] += prv;
        }
        if ( (mask >> s[i]) & 1 )
            prv++;
    }

    double best = (double)n * n;
    for ( int i = 0; i <= n; i++ ) {
        double cost = costPref[i] + expectedInversions( frecv[c][i] ) + costSuf[i + 1] + expectedInversions( frecv[c][n] - frecv[c][i] );
        best = min( best, cost );
    }

    return best;
}

int main() {
    cin >> s;
    n = s.size();
    s = " " + s;

    g = 0;
    for ( int i = 1; i <= n; i++ ) {
        if ( lit[s[i]] == 0 )
            lit[s[i]] = ++g;
        s[i] = lit[s[i]] - 1;
    }

    for ( int c = 0; c < g; c++ ) {
        for ( int i = 1; i <= n; i++ )
            frecv[c][i] = frecv[c][i - 1] + (s[i] == c);
    }

    cout << fixed << setprecision( 5 );
    for ( int mask = 1; mask < (1 << g); mask++ ) {
        dp[mask] = (double)n * n;
        for ( int c = 0; c < g; c++ ) {
            if ( (mask >> c) & 1 )
                dp[mask] = min( dp[mask], dp[mask - (1 << c)] + solve( c, mask - (1 << c) ) );
        }
    }

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

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2020 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 2392 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2648 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 2556 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 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 504 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 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 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 504 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 352 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 352 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 352 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 352 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 352 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 352 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 600 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 382 ms 1100 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 384 ms 1080 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 382 ms 1080 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 381 ms 856 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 373 ms 860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 374 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 374 ms 856 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 378 ms 1076 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 374 ms 860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 374 ms 1060 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2020 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 2392 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2648 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 2556 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 504 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 352 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 352 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 352 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 352 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 352 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 352 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 600 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 382 ms 1100 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 384 ms 1080 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 382 ms 1080 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 381 ms 856 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 373 ms 860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 374 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 374 ms 856 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 378 ms 1076 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 374 ms 860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 374 ms 1060 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 0 ms 348 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 49 ms 652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 2136 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 6 ms 2380 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 5 ms 2648 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 2644 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 436 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 448 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 384 ms 1072 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 383 ms 860 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 381 ms 856 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 384 ms 1080 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 374 ms 856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 375 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 372 ms 1060 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 376 ms 1312 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 375 ms 1068 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 377 ms 1060 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2045 ms 8272 KB Time limit exceeded
97 Halted 0 ms 0 KB -