Submission #1202296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202296		Unforgettablepl	Boarding Passes (BOI22_passes)	C++20	25 / 100	2093 ms	4740 KiB

passes

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    const int G = 15;
    vector<vector<int>> groups(G);
    string s;
    cin >> s;
    int N = s.size();
    for(int i=0;i<N;i++){
        groups[s[i]-'A'].emplace_back(i+1);
    }
    vector<int> DP((1<<G),1e12);
    DP[0]=0;
    for(int mask=1;mask<(1<<G);mask++){
        vector<pair<int,int>> arr;
        int tot = 0;
        for(int x=0;x<G;x++)if(mask&(1<<x)){
            for(int&i:groups[x])arr.emplace_back(i,x);
            tot+=groups[x].size();
        }
        ranges::sort(arr);
        for(int top=0;top<G;top++)if(mask&(1<<top)){
            int ans = 0;
            int currOther = 0;
            int currMine = 0;
            for(auto&[i,type]:arr){
                if(type!=top){
                    currOther++;
                    continue;
                }
                ans+=min(currMine+2ll*currOther,(int)((int)groups[top].size()-1ll-currMine+2ll*(tot-groups[top].size()-currOther)));
                currMine++;
            }
            DP[mask]=min(DP[mask],DP[mask^(1<<top)]+ans);
        }
    }
    cout << DP[(1<<G)-1]/2;
    if(DP[(1<<G)-1]&1)cout<<".5";
    cout << '\n';
}

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