Submission #602657

#	Time	Username	Problem	Language	Result	Execution time	Memory
602657		isaachew	Boarding Passes (BOI22_passes)	C++17	60 / 100	2080 ms	724 KiB

passes

#include <bits/stdc++.h>
/*
 Up to G boarding groups
 ST1: Expected number of passes for a boarding group of k from one end = 1/2 * current boarding group
 ST2: Check every permutation
 ST3: O(2^G*n)
 
 60/100?
 */
int main(){
    std::string gs;
    std::cin>>gs;
    int g=0;
    int n=gs.size();
    std::vector<int> counts(26,0);
    for(char i:gs){
        g=std::max(g,i-'A'+1);
        counts[i-'A']++;
    }
    if(1){
        std::vector<long long> mincost(1<<g,0);
        for(int i=1;i<1<<g;i++){
            long long mcsf=10000000000000000;
            for(int j=0;j<g;j++){
                if(((i>>j)&1)==0)continue;
                //if(counts[j]==0)continue;
                //std::cout<<i<<'/'<<(char)(j+'A')<<'\n';
                int cind=i^(1<<j);
                long long curcost=0;
                long long totalcost=counts[j];//twice total
                long long expcost=0;
                for(int r=0;r<g;r++){
                    if((cind>>r)&1){
                        totalcost+=counts[r]*2;
                    }
                }
                for(int k=0;k<n;k++){
                    int ln=gs[k]-'A';
                    if((cind>>ln)&1){
                        curcost+=2;
                    }
                    //std::cout<<curcost<<'/'<<totalcost-curcost-1<<' ';
                    if(ln==j){if(curcost*2>totalcost-1){
                        expcost+=totalcost-curcost-1;
                    }else{
                        expcost+=curcost;
                    }}
                    
                    if(ln==j){
                        curcost++;
                    }
                }
                //std::cout<<'\n';
                //std::cout<<"current "<<expcost<<", total "<<expcost+mincost[cind]<<'\n';
                mcsf=std::min(mcsf,expcost+mincost[cind]);
            }
            mincost[i]=mcsf;
        }
        long long val=mincost[(1<<g)-1];
        std::cout<<val/2;
        if(val&1)std::cout<<".5";
        std::cout<<'\n';
        return 0;
    }
}

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