Submission #851328

#	Time	Username	Problem	Language	Result	Execution time	Memory
851328		Ahmed57	Boarding Passes (BOI22_passes)	C++17	55 / 100	57 ms	92892 KiB

passes

#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
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40