oj.uz

Submission #851328

# Submission time Handle Problem Language Result Execution time Memory
851328 2023-09-19T14:58:46 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
55 / 100
 57 ms 92892 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++){
            int 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] = 10000000000000000.0;
    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;
                int 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;
            }
            int 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 2396 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 5076 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 4 ms 5292 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 Halted 0 ms 0 KB -

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 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 47452 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 5 ms 47452 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 5 ms 47608 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 5 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 5 ms 47452 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 47452 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 47448 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 47452 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 5 ms 47704 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 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 47452 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 5 ms 47452 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 5 ms 47608 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 5 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 5 ms 47452 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 47452 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 5 ms 47448 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 47452 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 5 ms 47704 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 6 ms 47452 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 6 ms 47448 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 5 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 37224 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 5 ms 47452 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 5 ms 47532 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 5 ms 47452 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 47452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 5 ms 47624 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 5 ms 47452 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 5 ms 47576 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 5 ms 47452 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 92724 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 28 ms 92712 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 24 ms 92892 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 29 ms 92820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 34 ms 92768 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 32 ms 92752 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 33 ms 92760 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 32 ms 92756 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 32 ms 92756 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 33 ms 92764 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 2396 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 5076 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 4 ms 5292 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 Halted 0 ms 0 KB -