oj.uz

Submission #723357

# Submission time Handle Problem Language Result Execution time Memory
723357 2023-04-13T16:04:10 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 377144 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];
    ll cr[G][N];
    ll cl[G][N];
    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 201 ms 376292 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 166 ms 376028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 186 ms 376284 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 198 ms 376280 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 185 ms 376268 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 253 ms 376808 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 264 ms 376824 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 250 ms 376828 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 271 ms 376860 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 376308 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 180 ms 376220 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 233 ms 376208 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 227 ms 376292 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 188 ms 376224 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 185 ms 376176 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 207 ms 376284 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 220 ms 376216 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 212 ms 376224 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 209 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 199 ms 376296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 241 ms 376304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 200 ms 376264 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 198 ms 376272 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 204 ms 376272 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 206 ms 376348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 194 ms 376240 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 376308 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 180 ms 376220 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 233 ms 376208 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 227 ms 376292 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 188 ms 376224 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 185 ms 376176 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 207 ms 376284 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 220 ms 376216 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 212 ms 376224 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 209 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 199 ms 376296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 241 ms 376304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 200 ms 376264 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 198 ms 376272 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 204 ms 376272 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 206 ms 376348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 194 ms 376240 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 187 ms 376336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 202 ms 376300 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 225 ms 376272 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 232 ms 376212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 230 ms 376300 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 180 ms 376304 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 216 ms 376296 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 218 ms 376176 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 210 ms 376260 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 201 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 213 ms 376304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 214 ms 376196 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 196 ms 376204 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 201 ms 376200 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 196 ms 376268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 250 ms 376300 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 192 ms 376360 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 183 ms 376528 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 193 ms 376400 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 309 ms 376448 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 259 ms 376396 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 242 ms 376428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 275 ms 376392 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 292 ms 376340 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 354 ms 376392 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 426 ms 376408 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 322 ms 376436 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 338 ms 376396 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 354 ms 376396 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 376292 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 166 ms 376028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 186 ms 376284 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 198 ms 376280 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 185 ms 376268 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 253 ms 376808 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 264 ms 376824 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 250 ms 376828 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 271 ms 376860 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 179 ms 376308 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 180 ms 376220 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 233 ms 376208 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 227 ms 376292 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 188 ms 376224 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 185 ms 376176 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 207 ms 376284 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 220 ms 376216 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 212 ms 376224 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 209 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 199 ms 376296 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 241 ms 376304 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 200 ms 376264 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 198 ms 376272 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 204 ms 376272 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 206 ms 376348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 194 ms 376240 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 187 ms 376336 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 202 ms 376300 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 225 ms 376272 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 232 ms 376212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 230 ms 376300 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 180 ms 376304 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 216 ms 376296 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 218 ms 376176 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 210 ms 376260 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 201 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 213 ms 376304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 214 ms 376196 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 196 ms 376204 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 201 ms 376200 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 196 ms 376268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 250 ms 376300 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 192 ms 376360 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 183 ms 376528 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 193 ms 376400 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 309 ms 376448 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 259 ms 376396 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 242 ms 376428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 275 ms 376392 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 292 ms 376340 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 354 ms 376392 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 426 ms 376408 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 322 ms 376436 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 338 ms 376396 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 354 ms 376396 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 183 ms 376192 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 196 ms 376248 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 182 ms 376300 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 145 ms 376036 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 182 ms 376304 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 166 ms 376380 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 181 ms 376304 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 244 ms 376864 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 233 ms 376844 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 230 ms 376912 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 238 ms 376824 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 197 ms 376264 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 179 ms 376336 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 208 ms 376304 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 228 ms 376240 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 179 ms 376220 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 196 ms 376304 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 224 ms 376296 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 233 ms 376352 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 183 ms 376240 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 187 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 183 ms 376272 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 220 ms 376268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 196 ms 376268 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 202 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 183 ms 376248 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 203 ms 376268 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 186 ms 376312 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 184 ms 376308 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 211 ms 376432 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 321 ms 376408 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 281 ms 376344 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 233 ms 376308 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 286 ms 376416 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 299 ms 376380 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 407 ms 376408 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 416 ms 376400 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 366 ms 376384 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 348 ms 376400 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 367 ms 376392 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 793 ms 376992 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 210 ms 376264 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 528 ms 376936 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 249 ms 376872 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 181 ms 376392 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 516 ms 376956 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 1888 ms 377144 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Execution timed out 2080 ms 377036 KB Time limit exceeded
104 Halted 0 ms 0 KB -