oj.uz

Submission #938536

# Submission time Handle Problem Language Result Execution time Memory
938536 2024-03-05T09:20:53 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 8068 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;
    double prvcost = best;
    bool cresc = false, ok = true;
    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 );
        //cout << cost << " ";
        if ( cresc ) {
            if ( prvcost > cost )
                ok = false;
        } else {
            if ( prvcost < cost )
                cresc = true;
        }
    }
    //cout << "\n";
    if ( !ok )
        exit( 1 );

    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 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2136 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 2392 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 2392 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 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 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 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 1 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 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 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 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 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 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 348 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 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 348 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 0 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 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 472 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 417 ms 1080 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 393 ms 1092 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 393 ms 1316 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 393 ms 856 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 388 ms 1048 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 385 ms 1048 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 385 ms 1048 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 383 ms 856 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 390 ms 1044 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 390 ms 1104 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 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2136 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 2392 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 2392 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 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 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 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 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 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 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 348 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 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 348 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 0 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 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 472 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 417 ms 1080 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 393 ms 1092 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 393 ms 1316 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 393 ms 856 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 388 ms 1048 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 385 ms 1048 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 385 ms 1048 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 383 ms 856 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 390 ms 1044 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 390 ms 1104 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 51 ms 616 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 344 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 1944 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 2392 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 5 ms 2392 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 2392 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 0 ms 348 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 348 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 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 600 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 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 0 ms 348 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 403 ms 860 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 391 ms 860 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 390 ms 1064 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 402 ms 1064 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 383 ms 1056 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 383 ms 1068 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 389 ms 1056 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 385 ms 856 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 384 ms 1068 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 386 ms 1052 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2021 ms 8068 KB Time limit exceeded
97 Halted 0 ms 0 KB -