oj.uz

Submission #625535

# Submission time Handle Problem Language Result Execution time Memory
625535 2022-08-10T14:30:14 Z Ooops_sorry Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 354140 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const int G = 15, N = 1e5 + 10;
const ld INF = 1e18;
ll L[G][G][N], R[G][G][N];
vector<int> pos[G];
int g;

//a * (a - 1) / 4

ld func(int a) {
    return (ld)a * (a - 1) / 4;
}

ll take_val(int mask, int j, int ind, bool f) {
    if (ind < 0 || ind >= pos[j].size()) return 0;
    ll res = 0;
    for (int i = 0; i < g; i++) {
        if (mask & (1 << i)) {
            if (!f) {
                res += L[j][i][pos[j][ind]];
            } else {
                res += R[j][i][pos[j][ind]];
            }
        }
    }
    return res;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> a(n);
    map<char, int> mp;
    for (int i = 0; i < s.size(); i++) {
        if (mp.count(s[i]) == 0) {
            mp[s[i]] = mp.size();
        }
        a[i] = mp[s[i]];
    }
    g = mp.size();
    vector<ld> dp((1 << g), INF);
    for (int i = 0; i < n; i++) {
        pos[a[i]].pb(i);
    }
    for (int i = 0; i < g; i++) {
        for (int l = 0; l < g; l++) {
            ll cnt = 0, res = 0;
            for (int j = 0; j < n; j++) {
                if (i == a[j]) {
                    res += cnt;
                    L[i][l][j] = res;
                } else if (l == a[j]){
                    cnt++;
                }
            }
            cnt = 0, res = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (i == a[j]) {
                    res += cnt;
                    R[i][l][j] = res;
                } else if (l == a[j]){
                    cnt++;
                }
            }
        }
    }
    dp[0] = 0;
    for (int mask = 0; mask < (1 << g); mask++) {
        for (int j = 0; j < g; j++) {
            if (!(mask & (1 << j))) {
                ld bst = func(pos[j].size()) + take_val(mask, j, 0, 1);
                for (int k = 0; k < pos[j].size(); k++) {
                    ld val = func(k + 1) + func((int)(pos[j].size()) - k - 1) + take_val(mask, j, k, 0) + take_val(mask, j, k + 1, 1);
                    bst = min(bst, val);
                }
                dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + bst);
            }
        }
    }
    cout << setprecision(30) << fixed << dp[(1 << g) - 1] << endl;
    return 0;
}

Compilation message

passes.cpp: In function 'long long int take_val(int, int, int, bool)':
passes.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if (ind < 0 || ind >= pos[j].size()) return 0;
      |                    ~~~~^~~~~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
passes.cpp:87:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                 for (int k = 0; k < pos[j].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 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 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2448 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2832 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2960 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 8 ms 2960 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 340 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 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 340 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 340 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 868 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 596 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 596 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 209 ms 17064 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 165 ms 3160 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 163 ms 3184 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 169 ms 8480 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 166 ms 16856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 167 ms 16812 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 201 ms 16852 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 197 ms 16724 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 177 ms 16724 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 194 ms 16824 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 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 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 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2448 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2832 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2960 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 8 ms 2960 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 340 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 340 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 868 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 596 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 596 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 209 ms 17064 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 165 ms 3160 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 163 ms 3184 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 169 ms 8480 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 166 ms 16856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 167 ms 16812 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 201 ms 16852 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 197 ms 16724 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 177 ms 16724 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 194 ms 16824 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 43 ms 3284 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 2448 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 2832 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 5 ms 2960 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 2960 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 724 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 596 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 596 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 176 ms 17100 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 162 ms 3156 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 174 ms 3188 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 163 ms 8440 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 169 ms 16972 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 246 ms 16816 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 201 ms 16852 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 227 ms 16828 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 171 ms 16820 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 177 ms 16820 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2054 ms 354140 KB Time limit exceeded
97 Halted 0 ms 0 KB -