oj.uz

Submission #1105040

# Submission time Handle Problem Language Result Execution time Memory
1105040 2024-10-25T08:31:37 Z MateiKing80 Boarding Passes (BOI22_passes) C++14
100 / 100
 275 ms 57660 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr ll INF = LLONG_MAX / 10;

int type_cnt;
int n;
vector<ll> cnt;
vector<vector<ll>> l, r;
vector<vector<vector<ll>>> l2, r2;
vector<vector<int>> groups;

ll get_cost(int already_boarded, int next, int split)
{
    ll result = 0;
    for(int t = 0; t < type_cnt; t ++)
    {
        ll tmp = l2[next][t][split] + r2[next][t][split];
        if (already_boarded & (1ll << t))
            result += 2 * tmp;
        else if (t == next)
            result += tmp;
    }
    return result;
}

ll get_cost(int already_boarded, int next)
{
    int mini = 0, maxi = groups[next].size() + 1;
    while (maxi - mini > 1)
    {
        int m1 = (maxi + mini) / 2 - 1;
        int m2 = m1 + 1;
        ll c1 = get_cost(already_boarded, next, m1);
        ll c2 = get_cost(already_boarded, next, m2);
        if (c1 < c2)
            maxi = m2;
        else mini = m1 + 1;
    }

    ll result = get_cost(already_boarded, next, mini);
    return result;
}

ll calc_costs()
{
    vector<ll> dp(1ll << type_cnt, INF);
    dp[0] = 0;
    for(int i = 1; i < 1ll << type_cnt; i ++)
    {
        for(int t = 0; t < type_cnt; t ++)
        {
            if (!(i & (1ll << t)))
                continue;
            int parent = i & ~(1ll << t);
            dp[i] = min(dp[i], dp[parent] + get_cost(parent, t));
        }
    }
    return dp[(1ll << type_cnt) - 1];
}

int main()
{
    string s;
    cin >> s;
    n = s.size();
    map<char, char> types;
    for (char& c: s)
    {
        if (!types.count(c))
        {
            char id = static_cast<char>(types.size());
            types[c] = id;
        }
        c = types[c];
    }

    type_cnt = types.size();
    cnt.assign(type_cnt, 0);
    for(char c: s)
        cnt[c] ++;

    groups.resize(type_cnt);
    for(int i = 0; i < n; i ++)
        groups[s[i]].push_back(i);

    l = r = vector<vector<ll>>(type_cnt, vector<ll>(n));
    vector<ll> tmp_cnt(type_cnt, 0);
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < type_cnt; j ++)
        {
            l[j][i] = tmp_cnt[j];
            r[j][i] = cnt[j] - tmp_cnt[j];
        }
        tmp_cnt[s[i]] ++;
        r[s[i]][i] --;
    }

    vector<vector<ll>> tmp_costs_l, tmp_costs_r;
    tmp_costs_l = tmp_costs_r = vector<vector<ll>>(type_cnt, vector<ll>(type_cnt, 0));
    l2 = r2 = vector<vector<vector<ll>>>(type_cnt, vector<vector<ll>>(type_cnt, {0}));

    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < type_cnt; j ++)
        {
            tmp_costs_l[s[i]][j] += l[j][i];
            tmp_costs_r[s[n - i - 1]][j] += r[j][n - i - 1];
        }
        for (int k = 0; k < type_cnt; ++k)
        {
            l2[s[i]][k].push_back(tmp_costs_l[s[i]][k]);
            r2[s[n - i - 1]][k].push_back(tmp_costs_r[s[n - i - 1]][k]);
        }
    }
    for(int i = 0; i < type_cnt; i ++)
        for(int j = 0; j < type_cnt; j ++)
            reverse(r2[i][j].begin(), r2[i][j].end());

    auto result = calc_costs();
    cout << result / 2 << ((result % 2) ? ".5" : "") << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 504 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 336 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 8 ms 4448 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 9 ms 4840 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 10 ms 5560 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 9 ms 5732 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 336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 336 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 336 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 504 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 336 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 336 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 336 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 336 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 336 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 336 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 504 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 336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 336 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 336 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 504 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 336 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 336 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 336 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 336 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 336 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 336 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 504 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 440 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 336 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 336 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 336 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 336 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 508 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 504 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 504 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 336 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 2 ms 848 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 8 ms 4344 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 7 ms 3664 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 7 ms 4432 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 6 ms 3664 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 8 ms 4432 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 7 ms 4284 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 8 ms 4344 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 8 ms 3920 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 7 ms 4176 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 8 ms 4176 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 504 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 336 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 8 ms 4448 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 9 ms 4840 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 10 ms 5560 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 9 ms 5732 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 336 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 336 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 504 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 336 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 336 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 336 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 336 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 336 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 336 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 504 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 440 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 336 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 336 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 336 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 336 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 508 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 504 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 504 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 336 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 336 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 2 ms 848 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 2 ms 848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 8 ms 4344 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 7 ms 3664 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 7 ms 4432 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 6 ms 3664 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 8 ms 4432 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 7 ms 4284 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 8 ms 4344 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 8 ms 3920 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 7 ms 4176 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 8 ms 4176 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 336 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 57 ms 592 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 336 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 336 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 336 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 8 ms 4572 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 9 ms 4840 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 9 ms 5508 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 9 ms 5560 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 508 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 336 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 744 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 336 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 336 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 500 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 336 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 336 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 336 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 336 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 336 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 504 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 336 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 336 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 336 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 592 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 2 ms 848 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 2 ms 848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 10 ms 4176 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 7 ms 3920 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 6 ms 4432 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 7 ms 3664 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 8 ms 4292 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 7 ms 4352 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 10 ms 4176 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 9 ms 4112 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 7 ms 4188 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 7 ms 4176 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 265 ms 53200 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 21 ms 592 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 259 ms 51968 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 136 ms 54192 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 36 ms 592 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 241 ms 52528 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 256 ms 54328 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 244 ms 54588 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 249 ms 55868 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 262 ms 54332 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 247 ms 54400 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 267 ms 54332 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 166 ms 49728 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 275 ms 57660 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'