oj.uz

Submission #723354

# Submission time Handle Problem Language Result Execution time Memory
723354 2023-04-13T16:02:21 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 377584 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
inline ll exp_inv(ll x) {
    return x * (x-1);
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    char a = 'A';
    string s; cin >> s;
    const int G = 15, N = 1e5;
    int n = s.size();
    if (n == 1) {
        cout << "0\n";
        return 0;
    }

    ll suml[G][G][N];
    ll sumr[G][G][N];
    memset(suml, 0 ,sizeof(suml));
    memset(sumr, 0 ,sizeof(sumr));
    vector cl(G, vector(n, 0ll));
    vector cr(G, vector(n, 0ll));
    vector ix(G, vector<int>());
    for (int c1 = 0; c1 < G; c1++) {
        for (int c2 = 0; c2 < G; c2++) {
            ll res = 0, cur = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == c1+a)
                    res += cur;
                else if (s[i] == c2+a)
                    cur++;
                suml[c1][c2][i] = res;
            }
        }
    }
    for (int c1 = 0; c1 < G; c1++) {
        for (int c2 = 0; c2 < G; c2++) {
            ll res = 0, cur = 0;
            for (int i = n-1; i >= 0; i --) {
                if (s[i] == c1+a)
                    res += cur;
                else if (s[i] == c2+a)
                    cur++;
                sumr[c1][c2][i] = res;
            }
        }
    }
    for (int j = 0; j < G; j++) {
        int c = 0;
        for (int i = 0; i < n;i ++) {
            if (s[i] == j+a)
                c++;
            cl[j][i] = c;
        }
    }
    for (int j = 0; j < G; j++) {
        int c = 0;
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == j+a)
                c++;
            cr[j][i] = c;
        }
    }
    for (int i = 0; i < n ;i++) 
        ix[s[i] - a].push_back(i);

    vector memo(1<<G, (ll)1e18);
    memo[(1<<G)-1] = 0;
    for (int used = (1<<G)-1-1; used >= 0; used--) {
        ll& res = memo[used];
        for (int i = 0 ;i < G; i++) {
            if (used&1<<i) continue;

            auto f = [&](int j) {
                ll sum = 0;
                for (int c2 = 0; c2 < G; c2++) {
                    if (used&1<<c2) {
                        if (j) sum += suml[i][c2][j-1];
                        if (j <n)sum += sumr[i][c2][j];
                    }
                }
                return sum * 4 + (j < n ? exp_inv(cr[i][j]) : 0) + (j ? exp_inv(cl[i][j-1]) : 0);
            };

            int l = -1, r = (int)ix[i].size()-2;
            while (l < r-1) {
                int m = (l+r) / 2;
                ll a = f(ix[i][m]), b = f(ix[i][m+1]);
                if (a == b) break;
                else if (a < b) r = m;
                else l = m;
            }
 
            for (int j = max(l-1, 0); j < min((int)ix[i].size(), 2 + max(0, r)); j++) {
                res = min(res, f(ix[i][j]) + memo[used |1<<i]);
            }
            res = min(res, f(0) + memo[used | 1<<i]);
            res = min(res, f(n) + memo[used | 1<<i]);
        }
    };
    ll ans;
    ans = memo[0];
 
    cout << ans / 4;
    if (ans%4 == 1) cout << ".25";
    if (ans%4 == 2) cout << ".5";
    if (ans%4== 3) cout << ".75";
    cout << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 352956 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 161 ms 352592 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 206 ms 352804 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 211 ms 352760 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 227 ms 352956 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 281 ms 372260 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 290 ms 375924 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 282 ms 377540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 289 ms 377480 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 352760 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 227 ms 352860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 257 ms 352728 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 233 ms 352840 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 222 ms 352764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 218 ms 352776 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 264 ms 352716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 233 ms 352940 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 219 ms 352820 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 228 ms 352716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 231 ms 352732 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 236 ms 352824 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 233 ms 352708 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 237 ms 352716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 224 ms 352816 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 243 ms 352716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 229 ms 352812 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 352760 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 227 ms 352860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 257 ms 352728 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 233 ms 352840 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 222 ms 352764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 218 ms 352776 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 264 ms 352716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 233 ms 352940 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 219 ms 352820 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 228 ms 352716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 231 ms 352732 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 236 ms 352824 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 233 ms 352708 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 237 ms 352716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 224 ms 352816 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 243 ms 352716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 229 ms 352812 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 214 ms 352800 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 230 ms 352948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 245 ms 352744 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 240 ms 352840 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 226 ms 352716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 205 ms 352796 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 238 ms 352796 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 242 ms 352820 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 218 ms 352924 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 226 ms 352808 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 246 ms 352804 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 220 ms 352768 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 238 ms 352820 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 221 ms 352716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 224 ms 352764 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 228 ms 352828 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 217 ms 352824 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 234 ms 355448 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 214 ms 355252 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 366 ms 355264 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 324 ms 355164 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 290 ms 355308 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 330 ms 355268 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 330 ms 355244 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 482 ms 355280 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 491 ms 355232 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 370 ms 355268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 386 ms 355236 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 423 ms 355196 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 352956 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 161 ms 352592 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 206 ms 352804 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 211 ms 352760 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 227 ms 352956 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 281 ms 372260 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 290 ms 375924 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 282 ms 377540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 289 ms 377480 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 212 ms 352760 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 227 ms 352860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 257 ms 352728 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 233 ms 352840 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 222 ms 352764 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 218 ms 352776 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 264 ms 352716 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 233 ms 352940 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 219 ms 352820 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 228 ms 352716 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 231 ms 352732 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 236 ms 352824 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 233 ms 352708 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 237 ms 352716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 224 ms 352816 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 243 ms 352716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 229 ms 352812 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 214 ms 352800 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 230 ms 352948 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 245 ms 352744 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 240 ms 352840 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 226 ms 352716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 205 ms 352796 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 238 ms 352796 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 242 ms 352820 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 218 ms 352924 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 226 ms 352808 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 246 ms 352804 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 220 ms 352768 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 238 ms 352820 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 221 ms 352716 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 224 ms 352764 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 228 ms 352828 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 217 ms 352824 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 234 ms 355448 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 214 ms 355252 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 366 ms 355264 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 324 ms 355164 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 290 ms 355308 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 330 ms 355268 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 330 ms 355244 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 482 ms 355280 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 491 ms 355232 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 370 ms 355268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 386 ms 355236 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 423 ms 355196 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 215 ms 352780 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 212 ms 352776 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 211 ms 353096 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 137 ms 352528 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 192 ms 352800 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 211 ms 352704 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 219 ms 352972 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 259 ms 372136 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 272 ms 375860 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 287 ms 377388 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 277 ms 377584 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 226 ms 352796 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 203 ms 352848 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 256 ms 352836 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 255 ms 352844 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 216 ms 352716 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 227 ms 352844 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 238 ms 352844 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 218 ms 352824 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 239 ms 352844 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 226 ms 352816 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 227 ms 352944 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 223 ms 352712 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 224 ms 352824 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 249 ms 352804 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 233 ms 352872 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 228 ms 352716 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 235 ms 352696 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 236 ms 355308 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 219 ms 355268 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 355 ms 355296 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 315 ms 355256 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 286 ms 355324 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 328 ms 355260 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 331 ms 355232 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 423 ms 355276 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 481 ms 355160 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 385 ms 355268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 350 ms 355264 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 420 ms 355216 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 747 ms 377268 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 264 ms 352796 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 509 ms 377084 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 290 ms 377484 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 215 ms 352700 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 623 ms 377192 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Execution timed out 2058 ms 377340 KB Time limit exceeded
103 Halted 0 ms 0 KB -