代码

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

// state: 0 unused, 1 a-only, 2 b-only, 3 both
static int state[200005];
static ll a[200005], b[200005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while(T--){
        int n, K, L; cin >> n >> K >> L;
        for(int i=0;i<n;i++) cin >> a[i];
        for(int i=0;i<n;i++) cin >> b[i];
        for(int i=0;i<n;i++) state[i]=0;

        vector<int> ordA(n), ordB(n);
        iota(ordA.begin(), ordA.end(), 0);
        iota(ordB.begin(), ordB.end(), 0);
        sort(ordA.begin(), ordA.end(), [&](int x,int y){ return a[x]>a[y]; });
        sort(ordB.begin(), ordB.end(), [&](int x,int y){ return b[x]>b[y]; });

        ll sum = 0;
        int overlap = 0;
        for(int t=0;t<K;t++){ int i = ordA[t]; state[i] |= 1; sum += a[i]; }
        for(int t=0;t<K;t++){
            int i = ordB[t];
            if(state[i]&1){ state[i]=3; overlap++; sum += b[i]; }
            else { state[i]=2; sum += b[i]; }
        }

        typedef pair<ll,int> P;
        priority_queue<P> qab0;      // max (a+b), state 0
        priority_queue<P, vector<P>, greater<P>> qamin; // min a, state 1
        priority_queue<P, vector<P>, greater<P>> qbmin; // min b, state 2
        priority_queue<P> qb1;       // max b, state 1
        priority_queue<P> qa2;       // max a, state 2
        priority_queue<P, vector<P>, greater<P>> qab3; // min (a+b), state 3

        for(int i=0;i<n;i++){
            if(state[i]==0) qab0.push({a[i]+b[i], i});
            else if(state[i]==1){ qamin.push({a[i],i}); qb1.push({b[i],i}); }
            else if(state[i]==2){ qbmin.push({b[i],i}); qa2.push({a[i],i}); }
            else { qab3.push({a[i]+b[i], i}); }
        }

        auto cl = [&](auto& pq, int need){
            while(!pq.empty() && state[pq.top().second]!=need) pq.pop();
        };

        while(overlap < L){
            cl(qab0,0); cl(qamin,1); cl(qbmin,2); cl(qb1,1); cl(qa2,2); cl(qab3,3);
            ll g1=LLONG_MIN, g2=LLONG_MIN, g3=LLONG_MIN, g4=LLONG_MIN;
            if(!qab0.empty() && !qamin.empty() && !qbmin.empty())
                g1 = qab0.top().first - qamin.top().first - qbmin.top().first;
            if(!qb1.empty() && !qbmin.empty())
                g2 = qb1.top().first - qbmin.top().first;
            if(!qa2.empty() && !qamin.empty())
                g3 = qa2.top().first - qamin.top().first;
            if(!qb1.empty() && !qa2.empty() && !qab3.empty())
                g4 = qb1.top().first + qa2.top().first - qab3.top().first;

            ll best = max(max(g1,g2), max(g3,g4));
            if(best == g1){
                int k=qab0.top().second, i=qamin.top().second, j=qbmin.top().second;
                state[k]=3; state[i]=0; state[j]=0;
                sum += g1;
                qab0.pop(); qamin.pop(); qbmin.pop();
                qab0.push({a[i]+b[i], i});
                qab0.push({a[j]+b[j], j});
                qab3.push({a[k]+b[k], k});
            } else if(best == g2){
                int k=qb1.top().second, j=qbmin.top().second;
                state[k]=3; state[j]=0;
                sum += g2;
                qb1.pop(); qbmin.pop();
                qab0.push({a[j]+b[j], j});
                qab3.push({a[k]+b[k], k});
            } else if(best == g3){
                int k=qa2.top().second, i=qamin.top().second;
                state[k]=3; state[i]=0;
                sum += g3;
                qa2.pop(); qamin.pop();
                qab0.push({a[i]+b[i], i});
                qab3.push({a[k]+b[k], k});
            } else {
                int i=qb1.top().second, j=qa2.top().second, k=qab3.top().second;
                state[i]=3; state[j]=3; state[k]=0;
                sum += g4;
                qb1.pop(); qa2.pop(); qab3.pop();
                qab3.push({a[i]+b[i], i});
                qab3.push({a[j]+b[j], j});
                qab0.push({a[k]+b[k], k});
            }
            overlap++;
        }
        cout << sum << "\n";
    }
    return 0;
}

评测结果