oj.uz

Submission #851329

# Submission time Handle Problem Language Result Execution time Memory
851329 2023-09-19T15:01:03 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
100 / 100
 1248 ms 179460 KB 
#include <bits/stdc++.h>
using namespace std;
int c = 0;
vector<int> arr[15];
long long lol[15][15][100001];
long long pref[100001],suf[100001];
long long dp[(1<<15)];
int sz;

int main(){
    string s;cin>>s;
    int n = s.size();
    map<char,int> x;
    int ind = -1;
    sz = s.size();
    for(auto i:s){
        ind++;
        if(x[i]==0){
            x[i] = ++c;
            arr[c-1].push_back(0);
            arr[c-1].push_back(ind);
        }else{
            arr[x[i]-1].push_back(ind);
        }
    }
    for(int i = 0;i<c;i++){
        for(int j = 0;j<c;j++){
            long long add = 2-(i==j) , cnt = 0;
            for(int e = 0;e<n;e++){
                pref[e] = (e?pref[e-1]:0)+((x[s[e]]-1)==i?cnt:0);
                cnt+=(x[s[e]]-1==j?add:0);
            }
            cnt = 0;
            for(int e = n-1;e>=0;e--){
                suf[e] = (e<n-1?suf[e+1]:0)+((x[s[e]]-1)==i?cnt:0);
                cnt+=(x[s[e]]-1==j?add:0);
            }
            for(auto d:arr[i]){
                lol[i][j][d] = pref[d]+suf[d+1];
                //cout<<lol[i][j][d]<<" "<<i<<" "<<j<<" "<<d<<endl;
            }
        }
    }
    for(int mask = (1<<c)-1;mask>=0;mask--){
    if(mask==(1<<c)-1){
        dp[mask] = 0;
        continue;
    }
    dp[mask] = 1e18;
    for(int j = 0;j<c;j++){
        if(!(mask&(1<<j))){
            int l=0,r=arr[j].size()-1;
            while(l<r){
                int mid = (l+r)/2;
                long long an = 0;
                for(int i=0;i<c;i++)if(!(mask&(1<<i)))an+=lol[j][i][arr[j][mid+1]]-lol[j][i][arr[j][mid]];
                if(an>=0)r = mid;
                else l = mid+1;
            }
            long long an = 0;
            for(int i=0;i<c;i++)if(!((mask&(1<<i))))an+=lol[j][i][arr[j][l]];
            dp[mask] = min(dp[mask],dp[mask^(1<<j)]+an);
        }
    }
    }
    cout<<setprecision(4)<<fixed<<dp[0]/2.l<<endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 4976 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 5076 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 5332 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 5332 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 6 ms 47616 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 5 ms 47448 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 5 ms 47452 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 5 ms 47452 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 6 ms 47452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 6 ms 47624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 5 ms 47452 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 5 ms 47452 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 47448 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 47452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 5 ms 47452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 5 ms 47612 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 47452 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 5 ms 47452 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 6 ms 47616 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 5 ms 47448 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 5 ms 47452 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 5 ms 47452 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 6 ms 47452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 4 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 6 ms 47624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 5 ms 47452 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 5 ms 47452 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 5 ms 47448 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 47452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 5 ms 47452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 5 ms 47612 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 6 ms 47452 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 5 ms 47452 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 6488 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 5 ms 47452 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 5 ms 47564 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 6 ms 47452 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 5 ms 47452 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 5 ms 47452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 4 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 5 ms 47448 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 5 ms 47452 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 5 ms 47604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 5 ms 47452 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 5 ms 47448 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 6 ms 47452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 5 ms 47448 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 5 ms 47452 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 5 ms 47552 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 2396 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 2396 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 57 ms 93088 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 29 ms 92764 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 25 ms 92760 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 29 ms 92756 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 32 ms 92756 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 31 ms 92756 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 32 ms 92752 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 31 ms 92752 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 34 ms 92860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 35 ms 92756 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 4976 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 5076 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 5332 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 5332 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 6 ms 47616 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 5 ms 47448 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 5 ms 47452 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 5 ms 47452 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 6 ms 47452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 4 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 6 ms 47624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 5 ms 47452 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 5 ms 47452 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 5 ms 47448 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 5 ms 47452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 5 ms 47452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 5 ms 47612 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 6 ms 47452 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 5 ms 47452 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 6488 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 5 ms 47452 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 5 ms 47564 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 6 ms 47452 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 5 ms 47452 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 5 ms 47452 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 4 ms 37212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 5 ms 47448 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 5 ms 47452 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 5 ms 47604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 5 ms 47452 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 5 ms 47448 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 6 ms 47452 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 5 ms 47448 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 5 ms 47452 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 5 ms 47552 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 2396 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 2396 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 57 ms 93088 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 29 ms 92764 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 25 ms 92760 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 29 ms 92756 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 32 ms 92756 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 31 ms 92756 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 32 ms 92752 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 31 ms 92752 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 34 ms 92860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 35 ms 92756 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 3 ms 29020 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 45 ms 176976 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 2396 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 2400 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 2656 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 5072 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 5076 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 5332 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 5188 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 7 ms 47548 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 5 ms 47452 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 5 ms 47452 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 5 ms 47452 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 5 ms 47568 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 4 ms 37356 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 5 ms 47452 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 5 ms 47452 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 5 ms 47452 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 5 ms 47448 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 6 ms 47452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 5 ms 47612 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 5 ms 47448 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 5 ms 47452 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 5 ms 47452 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 2396 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 2396 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 55 ms 92756 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 27 ms 92756 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 24 ms 92748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 28 ms 92764 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 32 ms 92804 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 31 ms 92764 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 32 ms 92748 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 32 ms 92756 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 37 ms 93024 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 32 ms 92756 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1248 ms 179144 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 33 ms 166696 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 489 ms 178072 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 448 ms 177616 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 44 ms 176964 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 529 ms 178000 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 677 ms 179096 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 693 ms 179384 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 679 ms 179044 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 690 ms 179460 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 665 ms 179028 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 684 ms 179152 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 546 ms 167804 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 661 ms 179232 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'