oj.uz

Submission #851331

# Submission time Handle Problem Language Result Execution time Memory
851331 2023-09-19T15:31:42 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
0 / 100
 8 ms 47580 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<<endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 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 8 ms 47580 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 47448 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Incorrect 5 ms 47448 KB 1st numbers differ - expected: '1.5000000000', found: '1.0000000000', error = '0.3333333333'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 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 8 ms 47580 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 47448 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Incorrect 5 ms 47448 KB 1st numbers differ - expected: '1.5000000000', found: '1.0000000000', error = '0.3333333333'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -