oj.uz

Submission #938609

# Submission time Handle Problem Language Result Execution time Memory
938609 2024-03-05T11:09:35 Z LucaIlie Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 342612 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];
long long costPref[MAX_G][MAX_G][MAX_N + 2], costSuf[MAX_G][MAX_G][MAX_N + 2];
unordered_map<char, int> lit;

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

double queryCost( int c, int mask, int i ) {
    double cost = expectedInversions( frecv[c][i] ) + expectedInversions( frecv[c][n] - frecv[c][i] );

    for ( int d = 0; d < g; d++ ) {
        if ( (mask >> d) & 1 )
            cost += costPref[c][d][i] + costSuf[c][d][i + 1];
    }

    return cost;
}

double solve( int c, int mask ) {
    double best = (double)n * n;

    //cout << c << "\n";
    for ( int i = 0; i <= n; i++ ) {
        double cost = queryCost( c, mask, i );
        if ( s[i] == c || ((mask >> s[i]) & 1) ) {
            //cout << cost << " ";
            best = min( best, cost );
        }
    }
    //cout << "\n" << best << "\n";

    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);
    }
    for ( int c = 0; c < g; c++ ) {
        for ( int d = 0; d < g; d++ ) {
            if ( c == d )
                continue;

            int cnt;

            cnt = 0;
            for ( int i = 1; i <= n; i++ ) {
                costPref[c][d][i] = costPref[c][d][i - 1];
                if ( s[i] == c )
                    costPref[c][d][i] += cnt;
                if ( s[i] == d )
                    cnt++;
            }
            cnt = 0;
            for ( int i = n; i >= 1; i-- ) {
                costSuf[c][d][i] = costSuf[c][d][i + 1];
                if ( s[i] == c )
                    costSuf[c][d][i] += cnt;
                if ( s[i] == d )
                    cnt++;
            }
        }
    }

    cout << fixed << setprecision( 1 );
    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 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 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 3 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 856 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 856 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 856 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 2 ms 1060 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 912 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1112 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 856 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 2 ms 1060 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 912 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1112 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 3 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 868 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 2 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 1012 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 913 ms 23912 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 755 ms 23916 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 717 ms 23644 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 733 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 914 ms 23392 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 819 ms 23388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 911 ms 23396 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 797 ms 23388 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 872 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 866 ms 23396 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 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 3 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 856 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 856 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 856 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 2 ms 1060 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 2 ms 912 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 2 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 2 ms 856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 1112 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 2 ms 856 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 3 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 868 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 860 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 2 ms 860 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 860 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 1012 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 913 ms 23912 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 755 ms 23916 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 717 ms 23644 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 733 ms 23644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 914 ms 23392 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 819 ms 23388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 911 ms 23396 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 797 ms 23388 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 872 ms 23388 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 866 ms 23396 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 604 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 247 ms 3140 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 348 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 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 848 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 856 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 852 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 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 3 ms 860 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 2 ms 860 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 2 ms 860 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 860 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 2 ms 860 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 856 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 860 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 860 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 2 ms 860 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 2 ms 860 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 860 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 2 ms 860 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 2 ms 1112 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 860 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 348 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 902 ms 23728 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 762 ms 23664 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 768 ms 23668 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 755 ms 23624 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 836 ms 23400 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 933 ms 23644 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 815 ms 23408 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 826 ms 23384 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 828 ms 23392 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 842 ms 23632 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2055 ms 342612 KB Time limit exceeded
97 Halted 0 ms 0 KB -