Submission #590309

#	Time	Username	Problem	Language	Result	Execution time	Memory
590309		jasmin	Boarding Passes (BOI22_passes)	C++14	100 / 100	776 ms	484632 KiB

passes

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int inf=1e18;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    int n=s.size();

    vector<int> a(n);
    map<int, int> num; int ind=1;
    vector<vector<int> > group(15, vector<int> (1, 0));
    for(int i=0; i<n; i++){
        if(num[s[i]]==0){
            num[s[i]]=ind;
            ind++;
        }
        a[i]=num[s[i]]-1;
        group[a[i]].push_back(i);
    }
    int g=ind-1;
    for(int i=0; i<15; i++){
        group[i].push_back(n-1);
    }

    vector<vector<int> > prefix(n+1, vector<int> (g, 0));
    vector<vector<int> > suffix(n+1, vector<int> (g, 0)); //exklusiv
    for(int i=0; i<n; i++){
        prefix[i+1]=prefix[i];
        prefix[i+1][a[i]]++;
    }
    for(int i=n-1; i>0; i--){
        suffix[i-1]=suffix[i];
        suffix[i-1][a[i]]++;
    }
    vector<vector<vector<int> > > prefixsum(n+1, vector<vector<int> > (g, vector<int> (g, 0)));
    vector<vector<vector<int> > > suffixsum(n+1, vector<vector<int> > (g, vector<int> (g, 0)));
    for(int i=1; i<n; i++){
        prefixsum[i]=prefixsum[i-1];
        for(int j=0; j<g; j++){
            prefixsum[i][a[i]][j]+=prefix[i][j];
        }
    }
    for(int i=n-2; i>=0; i--){
        suffixsum[i]=suffixsum[i+1];
        for(int j=0; j<g; j++){
            suffixsum[i][a[i]][j]+=suffix[i][j];
        }
    }


    auto cost=[&](int mask, int lastgroup, int lastleft){
        if(lastleft+1==(int)group[lastgroup].size()){
            return inf;
        }

        int indleft=group[lastgroup][lastleft];
        int indright=group[lastgroup][lastleft+1];
        //cout << "left: " << indleft << " right: " << indright << "\n" << flush;

        int ans=0;
        for(int i=0; i<g; i++){
            if((mask>>i)%2==0 || i==lastgroup) continue;
            ans+=prefixsum[indleft][lastgroup][i]*2;
            ans+=suffixsum[indright][lastgroup][i]*2;
        }
        ans+=prefixsum[indleft][lastgroup][lastgroup];
        ans+=suffixsum[indright][lastgroup][lastgroup];
        return ans;
    };
    auto mincost=[&](int mask, int lastgroup){
        //cout << "mincost:\n";
        //cout << "mask: " << mask << " last group: " << lastgroup << "\n";
        int l=0; int r=group[lastgroup].size()-2;
        int ans=r;
        while(l<=r){
            //cout << "bs " << l << " " << r << "\n" << flush;
            int m=l+(r-l)/2;
            if(cost(mask, lastgroup, m)<=cost(mask, lastgroup, m+1)){
                ans=m;
                r=m-1;
            }
            else{
                l=m+1;
            }
        }
        //cout << "mincost " << mask << " " << lastgroup << " " << ans << " " << cost(mask, lastgroup, ans) << "\n" << flush;
        return cost(mask, lastgroup, ans);
    };


    vector<int> dp((1<<g), inf);
    dp[0]=0;
    for(int i=1; i<(1<<g); i++){
        for(int last=0; last<g; last++){
            if((i>>last)%2==0) continue;

            dp[i]=min(dp[i], dp[i-(1<<last)]+mincost(i, last));
        }
        //cout << i << " " << dp[i] << "\n" << flush;
    }
    double ans=(double)dp[(1<<g)-1]/(double)2;
    cout.precision(100);
    cout << ans << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40