oj.uz

Submission #722940

# Submission time Handle Problem Language Result Execution time Memory
722940 2023-04-13T06:05:08 Z dxz05 Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 2064 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

long long exp_inv(ll n){
    return (long double) n * (n - 1); // should be divided by 4
}

ll dp[1 << 15];

void solve(){
    string s;
    cin >> s;
    int n = (int)s.size();

    vector<vector<int>> pos;
    map<char, int> id;

    for (int i = 0; i < n; i++){
        if (id.find(s[i]) == id.end()){
            id[s[i]] = (int) id.size();
            pos.emplace_back();
        }
        pos[id[s[i]]].push_back(i);
    }

    int G = (int) pos.size();

    int m1 = (n - 1) / 2;
    int m2 = m1 + 1;

    long double ans = 5e18;

    fill(dp, dp + (1 << G), 5e18);

    dp[0] = 0;

    for (int mask = 0; mask < (1 << G); mask++){
        if (dp[mask] >= 1e18) continue;

        vector<int> cnt(n, 0);
        for (int c = 0; c < G; c++){
            if (mask & (1 << c)){
                for (int i : pos[c]) cnt[i] = 1;
            }
        }

        for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];

        for (int c = 0; c < G; c++){
            if (mask & (1 << c)) continue;

            int sz = (int) pos[c].size();

            long long sum_l = 0;
            vector<int> diff;

            for (int i : pos[c]){
                int l = cnt[i];
                int r = cnt.back() - cnt[i];
                sum_l += l;
                diff.push_back(r - l);
            }

            sort(all(diff));

            long long cur = 5e18;
            for (int half = 0; half <= sz; half++){
                if (half > 0) sum_l += diff[half - 1];
                cur = min(cur, sum_l * 4 + exp_inv(half) + exp_inv(sz - half));
            }

            int new_mask = mask | (1 << c);
            dp[new_mask] = min(dp[new_mask], dp[mask] + cur);
        }

    }

    cout << fixed << setprecision(5);
    cout << (long double) dp[(1 << G) - 1] / 4 << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

Compilation message

passes.cpp: In function 'void solve()':
passes.cpp:35:9: warning: unused variable 'm2' [-Wunused-variable]
   35 |     int m2 = m1 + 1;
      |         ^~
passes.cpp:37:17: warning: unused variable 'ans' [-Wunused-variable]
   37 |     long double ans = 5e18;
      |                 ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 1808 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 1936 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 1936 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 1936 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 328 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 300 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 2 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 464 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 138 ms 468 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 230 ms 428 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 202 ms 544 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 184 ms 444 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 137 ms 468 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 132 ms 468 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 132 ms 468 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 189 ms 468 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 156 ms 468 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 175 ms 468 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 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 1808 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 1936 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 1936 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 1936 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 2 ms 332 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 328 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 300 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 328 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 2 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 2 ms 464 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 138 ms 468 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 230 ms 428 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 202 ms 544 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 184 ms 444 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 137 ms 468 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 132 ms 468 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 132 ms 468 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 189 ms 468 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 156 ms 468 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 175 ms 468 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 212 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 45 ms 564 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 328 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 7 ms 1936 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 6 ms 2064 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 8 ms 2064 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 2064 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 332 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 332 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 324 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 2 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 177 ms 468 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 377 ms 432 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 271 ms 544 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 150 ms 340 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 130 ms 472 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 145 ms 480 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 187 ms 468 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 128 ms 468 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 174 ms 484 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 171 ms 468 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2045 ms 1748 KB Time limit exceeded
97 Halted 0 ms 0 KB -