제출 #1202333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202333		Unforgettablepl	Boarding Passes (BOI22_passes)	C++20	100 / 100	311 ms	381900 KiB

passes

#pragma GCC optimize("Ofast","unroll-loops")
#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();
    vector<vector<int>> peopleBeforeInGroup(N+1,vector<int>(G));
    for(int i=0;i<N;i++){
        groups[s[i]-'A'].emplace_back(i+1);
        peopleBeforeInGroup[i+1]=peopleBeforeInGroup[i];
        peopleBeforeInGroup[i+1][s[i]-'A']++;
    }
    vector prefixAns(G,vector (G,vector (N+1,0ll)));
    vector suffixAns(G,vector (G,vector (N+1,0ll)));
    for(int top=0;top<G;top++){
        for(int bottom=0;bottom<G;bottom++){
            for(int idx=0;idx<groups[top].size();idx++){
                int i = groups[top][idx];
                if(idx)prefixAns[top][bottom][idx]=prefixAns[top][bottom][idx-1];
                prefixAns[top][bottom][idx]+=2ll*peopleBeforeInGroup[i-1][bottom];
            }
            for(int idx=groups[top].size()-1;idx>=0;idx--){
                int i = groups[top][idx];
                if(idx!=N)suffixAns[top][bottom][idx]=suffixAns[top][bottom][idx+1];
                suffixAns[top][bottom][idx]+=2ll*(groups[bottom].size()-peopleBeforeInGroup[i][bottom]);
            }
        }
        for(int&i:prefixAns[top][top])i/=2;
        for(int&i:suffixAns[top][top])i/=2;
    }
    vector<int> DP((1<<G),1e12);
    DP[0]=0;
    for(int mask=1;mask<(1<<G);mask++){
        int tot = 0;
        for(int x=0;x<G;x++)if(mask&(1<<x)){
            tot+=groups[x].size();
        }
        for(int top=0;top<G;top++)if(mask&(1<<top)){
            int ans = 0;
            int breakPoint = lower_bound(groups[top].begin(),groups[top].end(),0,[&](const int x,const int b){
                int currMine = peopleBeforeInGroup[x][top]-1;
                int currOther = 0;
                for(int i=0;i<G;i++)if((mask&(1<<i)) and i!=top)currOther+=peopleBeforeInGroup[x][i];
                return currMine+2ll*currOther<=groups[top].size()-1ll-currMine+2ll*(tot-groups[top].size()-currOther);
            }) - groups[top].begin();
            for(int i=0;i<G;i++)if(mask&(1<<i)){
                if(breakPoint)ans+=prefixAns[top][i][breakPoint-1];
                if(breakPoint<groups[top].size())ans+=suffixAns[top][i][breakPoint];
            }
            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: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40