oj.uz

Submission #723360

# Submission time Handle Problem Language Result Execution time Memory
723360 2023-04-13T16:07:25 Z dxz05 Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 1172 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 long) 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();

    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 mn = 5e18;
            for (int half = 0; half <= sz; half++){
                ll cur = 0;

                for (int i = 0; i < sz; i++){
                    int j = pos[c][i];
                    if (i < half){
                        cur += cnt[j];
                    } else {
                        cur += cnt.back() - cnt[j];
                    }
                }

                cur *= 4;
                cur += exp_inv(half) + exp_inv(sz - half);

                mn = min(mn, cur);
            }

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

    }

    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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 0 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 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2057 ms 1172 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 1 ms 212 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 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 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 0 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 1 ms 212 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 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 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 0 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 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 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 212 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 0 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 212 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 0 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 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 0 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 92 ms 432 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 84 ms 340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2070 ms 340 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 0 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 1 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2057 ms 1172 KB Time limit exceeded
7 Halted 0 ms 0 KB -