oj.uz

Submission #723380

# Submission time Handle Problem Language Result Execution time Memory
723380 2023-04-13T16:23:37 Z drdilyor Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 377008 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;
#define time(code) {auto _s = chrono::high_resolution_clock::now(); code;cerr << (chrono::high_resolution_clock::now() - _s).count() / 1e9 << '\n';}
 
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];
    int cnt[G]{};
    vector ix(G, vector<int>());

    time(({
        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++)
            cnt[s[i] - a]++;
        for (int i = 0; i < G; i++)
            ix[i].reserve(cnt[i]);
        for (int i = 0; i < n ;i++) 
            ix[s[i] - a].push_back(i);
    }));

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

            auto f = [&](int j) {
                ll sum = 0;
                for (int k = 0; k < G; k++) {
                    int c2 = k;
                    if (used>>c2&1) {
                        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(), 3 + 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 238 ms 376196 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 157 ms 376272 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 193 ms 376212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 195 ms 376296 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 216 ms 376184 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 250 ms 376820 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 272 ms 376984 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 265 ms 376984 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 263 ms 376976 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 376288 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 220 ms 376276 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 227 ms 376188 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 303 ms 376268 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 189 ms 376268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 216 ms 376196 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 293 ms 376228 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 206 ms 376288 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 289 ms 376296 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 249 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 226 ms 376344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 225 ms 376224 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 209 ms 376308 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 210 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 285 ms 376244 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 264 ms 376264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 210 ms 376232 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 376288 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 220 ms 376276 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 227 ms 376188 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 303 ms 376268 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 189 ms 376268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 216 ms 376196 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 293 ms 376228 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 206 ms 376288 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 289 ms 376296 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 249 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 226 ms 376344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 225 ms 376224 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 209 ms 376308 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 210 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 285 ms 376244 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 264 ms 376264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 210 ms 376232 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 186 ms 376268 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 195 ms 376248 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 233 ms 376296 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 225 ms 376288 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 215 ms 376184 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 240 ms 376256 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 225 ms 376268 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 253 ms 376232 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 219 ms 376348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 246 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 200 ms 376292 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 205 ms 376200 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 220 ms 376288 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 235 ms 376180 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 195 ms 376208 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 199 ms 376264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 240 ms 376268 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 190 ms 376260 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 264 ms 376340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 360 ms 376360 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 284 ms 376260 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 280 ms 376348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 312 ms 376368 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 309 ms 376352 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 432 ms 376352 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 573 ms 376352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 350 ms 376268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 367 ms 376360 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 451 ms 376356 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 376196 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 157 ms 376272 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 193 ms 376212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 195 ms 376296 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 216 ms 376184 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 250 ms 376820 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 272 ms 376984 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 265 ms 376984 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 263 ms 376976 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 199 ms 376288 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 220 ms 376276 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 227 ms 376188 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 303 ms 376268 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 189 ms 376268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 216 ms 376196 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 293 ms 376228 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 206 ms 376288 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 289 ms 376296 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 249 ms 376292 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 226 ms 376344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 225 ms 376224 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 209 ms 376308 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 210 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 285 ms 376244 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 264 ms 376264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 210 ms 376232 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 186 ms 376268 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 195 ms 376248 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 233 ms 376296 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 225 ms 376288 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 215 ms 376184 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 240 ms 376256 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 225 ms 376268 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 253 ms 376232 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 219 ms 376348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 246 ms 376296 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 200 ms 376292 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 205 ms 376200 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 220 ms 376288 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 235 ms 376180 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 195 ms 376208 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 199 ms 376264 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 240 ms 376268 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 190 ms 376260 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 264 ms 376340 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 360 ms 376360 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 284 ms 376260 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 280 ms 376348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 312 ms 376368 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 309 ms 376352 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 432 ms 376352 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 573 ms 376352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 350 ms 376268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 367 ms 376360 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 451 ms 376356 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 202 ms 376268 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 202 ms 376204 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 195 ms 376268 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 183 ms 376244 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 179 ms 376200 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 203 ms 376268 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 197 ms 376384 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 255 ms 377008 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 263 ms 376872 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 251 ms 377008 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 267 ms 376908 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 207 ms 376384 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 196 ms 376296 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 238 ms 376208 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 214 ms 376340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 219 ms 376296 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 201 ms 376292 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 234 ms 376400 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 220 ms 376276 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 220 ms 376264 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 229 ms 376300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 228 ms 376164 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 259 ms 376288 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 214 ms 376296 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 256 ms 376268 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 208 ms 376292 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 210 ms 376288 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 214 ms 376248 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 207 ms 376368 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 251 ms 376368 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 382 ms 376360 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 291 ms 376360 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 303 ms 376368 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 334 ms 376268 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 292 ms 376356 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 419 ms 376356 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 460 ms 376352 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 359 ms 376356 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 345 ms 376356 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 398 ms 376356 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 878 ms 376900 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 262 ms 376232 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 512 ms 376800 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 271 ms 376892 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 255 ms 376192 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 582 ms 376904 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Execution timed out 2058 ms 376868 KB Time limit exceeded
103 Halted 0 ms 0 KB -