oj.uz

Submission #748643

# Submission time Handle Problem Language Result Execution time Memory
748643 2023-05-26T16:51:26 Z inventiontime Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 3524 KB 
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;

double cst(int x) {
    return (double) x * (x-1) / 4;
}

void solve() {


    string s;
    cin >> s;
    int n = s.size();
    vvi pos(26);
    loop(i, n) 
        pos[s[i]-'A'].pb(i);
    vi ch;
    loop(i, 26) if(!pos[i].empty())
        ch.pb(i);
    int g = ch.size();
    vi id(26);
    loop(i, g) id[ch[i]] = i;

    if(g == 1) {
        cout << setprecision(16) << cst(n/2) + cst((n+1)/2) << endl;
        return;
    }


    vd dp(1 << g, inf);
    dp[0] = 0;
    loop(pre, 1 << g) {
        bitset<15> prev(pre);
        loop(ch, g) if(!prev[ch]) {
            int nxt = pre + (1 << ch);
            double cost = inf;

            vd left(n);
            vd right(n+1);
            int cnt = 0, oth = 0;
            for(int i = 0; i < n; i++) {
                if(i) left[i] = left[i-1];
                if(prev[id[s[i]-'A']]) oth++;
                else if(id[s[i]-'A'] == ch) {
                    cnt++;
                    left[i] += oth;
                    left[i] += cst(cnt);
                    left[i] -= cst(cnt-1);
                }
            }
            cnt = 0, oth = 0;
            for(int i = n-1; i >= 0; i--) {
                right[i] = right[i+1];
                if(prev[id[s[i]-'A']]) oth++;
                else if(id[s[i]-'A'] == ch) {
                    cnt++;
                    right[i] += oth;
                    right[i] += cst(cnt);
                    right[i] -= cst(cnt-1);
                }
            }

            loop(i, n)
                ckmin(cost, left[i] + right[i+1]);

            ckmin(dp[nxt], dp[pre] + cost);
        }
    }


    cout << setprecision(16) << dp[(1 << g) - 1] << endl;

}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 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 Correct 2 ms 1680 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1680 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1680 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1680 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 276 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 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 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 0 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 276 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 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 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 0 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 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 0 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 0 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 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 212 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 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 0 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 888 ms 820 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 411 ms 688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 360 ms 636 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 415 ms 708 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 413 ms 688 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 404 ms 820 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 412 ms 728 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 399 ms 716 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 403 ms 644 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 399 ms 640 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 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 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 Correct 2 ms 1680 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1680 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1680 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1680 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 276 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 212 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 212 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 0 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 0 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 212 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 0 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 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 212 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 0 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 212 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 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 0 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 888 ms 820 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 411 ms 688 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 360 ms 636 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 415 ms 708 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 413 ms 688 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 404 ms 820 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 412 ms 728 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 399 ms 716 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 403 ms 644 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 399 ms 640 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 79 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 320 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 320 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 320 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 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 1680 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 1800 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 1804 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 1804 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 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 320 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 212 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 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 212 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 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 320 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 1 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 464 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 870 ms 796 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 408 ms 640 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 363 ms 620 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 419 ms 792 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 408 ms 644 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 406 ms 652 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 409 ms 644 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 409 ms 708 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 405 ms 644 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 406 ms 640 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2078 ms 3524 KB Time limit exceeded
97 Halted 0 ms 0 KB -