oj.uz

Submission #625519

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

using namespace std;

mt19937 rnd(51);

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

const ld INF = 1e18;

//a * (a - 1) / 4

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

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]];
    }
    int g = mp.size();
    vector<ld> dp((1 << g), INF);
    vector<vector<int>> pos(g);
    vector<vector<vector<ll>>> L(g, vector<vector<ll>>(g, vector<ll>(n))), R(g, vector<vector<ll>>(g, vector<ll>(n)));
    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 i = 0; i < (1 << g); i++) {
        for (int j = 0; j < g; j++) {
            if (!(i & (1 << j))) {
                ld bst = func(pos[j].size());
                for (int k = 0; k < g; k++) {
                    if (i & (1 << k)) {
                        bst += R[j][k][pos[j][0]];
                    }
                }
                for (int k = 0; k < pos[j].size(); k++) {
                    ld val = func(k + 1) + func((int)(pos[j].size()) - k - 1);
                    for (int l = 0; l < g; l++) {
                        if (i & (1 << l)) {
                            val += L[j][l][pos[j][k]];
                            if (k + 1 < pos[j].size()) {
                                val += R[j][l][pos[j][k + 1]];
                            }
                        }
                    }
                    bst = min(bst, val);
                }
                dp[i + (1 << j)] = min(dp[i + (1 << j)], dp[i] + bst);
            }
        }
    }
    cout << setprecision(30) << fixed << dp[(1 << g) - 1] << endl;
    return 0;
}

Compilation message

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

Subtask #1
5.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 1 ms 320 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 3332 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3860 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4148 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4144 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 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 224 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 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 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 224 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 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 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 288 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 328 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 116 ms 16912 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 96 ms 16912 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 93 ms 16844 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 116 ms 16852 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 132 ms 16468 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 129 ms 16468 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 102 ms 16564 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 119 ms 16588 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 127 ms 16564 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 121 ms 16568 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 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 320 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 3332 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 3860 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4148 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4144 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 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 224 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 288 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 328 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 116 ms 16912 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 96 ms 16912 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 93 ms 16844 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 116 ms 16852 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 132 ms 16468 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 129 ms 16468 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 102 ms 16564 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 119 ms 16588 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 127 ms 16564 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 121 ms 16568 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 32 ms 960 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 0 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 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 324 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 3332 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 5 ms 3856 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 5 ms 4196 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 4148 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 212 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 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 324 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 0 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 340 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 141 ms 16924 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 94 ms 16924 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 92 ms 16840 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 102 ms 16852 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 101 ms 16648 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 106 ms 16564 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 130 ms 16468 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 110 ms 16468 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 138 ms 16520 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 136 ms 16564 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2083 ms 366912 KB Time limit exceeded
97 Halted 0 ms 0 KB -