제출 #581177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581177		jasmin	Boarding Passes (BOI22_passes)	C++17	60 / 100	2074 ms	3644 KiB

passes

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

int inf=1e18;

int cost(int last, int mask, vector<int>& group, int n){
    vector<int> prefix(n+1);
    vector<int> suffix(n+1);
    for(int i=0; i<n; i++){
        prefix[i+1]=prefix[i];
        if(group[i]==last){
            prefix[i+1]+=1;
        }
        else if((mask>>group[i])%2==1){
            prefix[i+1]+=2;
        }
    }
    for(int i=n-1; i>=0; i--){
        suffix[i]=suffix[i+1];
        if(group[i]==last){
            suffix[i]+=1;
        }
        else if((mask>>group[i])%2==1){
            suffix[i]+=2;
        }
    }

    int ans=0;
    for(int i=0; i<n; i++){
        if(group[i]!=last) continue;
        ans+=min(prefix[i], suffix[i+1]);
        //cout << i << " " << prefix[i] << " " << suffix[i+1] << " " << ans << "\n";
    }
    //cout << ans << "\n";
    return ans;
}

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

    string s;
    cin >> s;
    set<int> b;
    int n=s.size();
    vector<int> group(n);
    for(int i=0; i<n; i++){
        b.insert(s[i]);
    }
    int g=b.size();
    int ind=0;
    map<int,int> num;
    for(auto e: b){
        num[e]=ind;
        ind++;
    }
    for(int i=0; i<n; i++){
        group[i]=num[s[i]];
    }

    vector<int> dp((1<<g), inf);
    dp[0]=0;
    //cout << n << " " << g << "<n";
    for(int i=1; i<(1<<g); i++){

        for(int last=0; last<g; last++){
            if((i>>last)%2==0) continue;
            //cout << dp[i] << " " << dp[i-(1<<last)] << " " << cost(last, i, group, n) << "\n";
            dp[i]=min(dp[i], dp[i-(1<<last)]+cost(last, i, group, n));
        }
    }

    double ans=(double)(dp[(1<<g)-1])/2;
    //cout << "hallo\n";
    //cout << dp[(1<<g)-1] << " " << dp[1] << " " << cost(0, 1, group, n) << "\n";
    cout.precision(100);
    cout << ans << "\n";
}

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