代码

#include <sys/auxv.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

#define MAXN 200005
static int state[MAXN];
static ll a[MAXN], b[MAXN];
static int idx[MAXN];

struct Node { ll k; int i; };

static Node h0[MAXN]; static int s0;   // max (a+b), state 0
static Node h1n[MAXN]; static int s1n; // min a,      state 1
static Node h2n[MAXN]; static int s2n; // min b,      state 2
static Node h1b[MAXN]; static int s1b; // max b,      state 1
static Node h2a[MAXN]; static int s2a; // max a,      state 2
static Node h3n[MAXN]; static int s3n; // min (a+b),  state 3

static inline void pushmax(Node* h, int& s, ll k, int i){
    int c = ++s;
    while(c > 1){
        int p = c>>1;
        if(h[p].k >= k) break;
        h[c] = h[p]; c = p;
    }
    h[c].k = k; h[c].i = i;
}
static inline void pushmin(Node* h, int& s, ll k, int i){
    int c = ++s;
    while(c > 1){
        int p = c>>1;
        if(h[p].k <= k) break;
        h[c] = h[p]; c = p;
    }
    h[c].k = k; h[c].i = i;
}
static inline void popmax(Node* h, int& s){
    Node last = h[s--];
    int c = 1;
    while((c<<1) <= s){
        int l = c<<1, r = l|1;
        int ch = (r<=s && h[r].k > h[l].k) ? r : l;
        if(h[ch].k <= last.k) break;
        h[c] = h[ch]; c = ch;
    }
    h[c] = last;
}
static inline void popmin(Node* h, int& s){
    Node last = h[s--];
    int c = 1;
    while((c<<1) <= s){
        int l = c<<1, r = l|1;
        int ch = (r<=s && h[r].k < h[l].k) ? r : l;
        if(h[ch].k >= last.k) break;
        h[c] = h[ch]; c = ch;
    }
    h[c] = last;
}
static inline void cleanmax(Node* h, int& s, int need){
    while(s && state[h[1].i] != need) popmax(h, s);
}
static inline void cleanmin(Node* h, int& s, int need){
    while(s && state[h[1].i] != need) popmin(h, s);
}

static inline ll rdll(const char*& p){
    while(*p < '0' || *p > '9') p++;
    ll v = 0;
    while(*p >= '0' && *p <= '9'){ v = v*10 + (*p - '0'); p++; }
    return v;
}

static char obuf[1<<20];
static int optr;

static inline void putint(ll x){
    char tmp[24]; int t=0;
    if(x==0){ obuf[optr++]='0'; obuf[optr++]='\n'; return; }
    while(x>0){ tmp[t++] = '0' + (x%10); x/=10; }
    while(t--) obuf[optr++] = tmp[t];
    obuf[optr++] = '\n';
}

int main(){
    struct DuckInfo* d = (struct DuckInfo*)getauxval(0x6b637564);
    if(!d) return 1;
    const char* p = d->stdin_ptr;
    int T = (int)rdll(p);
    while(T--){
        int n = (int)rdll(p);
        int K = (int)rdll(p);
        int L = (int)rdll(p);
        for(int i=0;i<n;i++) a[i] = rdll(p);
        for(int i=0;i<n;i++) b[i] = rdll(p);
        for(int i=0;i<n;i++) state[i] = 0;

        for(int i=0;i<n;i++) idx[i]=i;
        nth_element(idx, idx+K, idx+n, [&](int x,int y){ return a[x]>a[y]; });
        ll sum = 0;
        for(int t=0;t<K;t++){ int i=idx[t]; state[i]=1; sum+=a[i]; }
        for(int i=0;i<n;i++) idx[i]=i;
        nth_element(idx, idx+K, idx+n, [&](int x,int y){ return b[x]>b[y]; });
        int overlap = 0;
        for(int t=0;t<K;t++){
            int i=idx[t];
            if(state[i]==1){ state[i]=3; overlap++; sum+=b[i]; }
            else { state[i]=2; sum+=b[i]; }
        }

        s0=s1n=s2n=s1b=s2a=s3n=0;
        for(int i=0;i<n;i++){
            if(state[i]==0){ pushmax(h0,s0,a[i]+b[i],i); }
            else if(state[i]==1){ pushmin(h1n,s1n,a[i],i); pushmax(h1b,s1b,b[i],i); }
            else if(state[i]==2){ pushmin(h2n,s2n,b[i],i); pushmax(h2a,s2a,a[i],i); }
            else { pushmin(h3n,s3n,a[i]+b[i],i); }
        }

        while(overlap < L){
            cleanmax(h0,s0,0);
            cleanmin(h1n,s1n,1);
            cleanmin(h2n,s2n,2);
            cleanmax(h1b,s1b,1);
            cleanmax(h2a,s2a,2);
            cleanmin(h3n,s3n,3);

            ll g1=LLONG_MIN, g2=LLONG_MIN, g3=LLONG_MIN, g4=LLONG_MIN;
            if(s0 && s1n && s2n) g1 = h0[1].k - h1n[1].k - h2n[1].k;
            if(s1b && s2n) g2 = h1b[1].k - h2n[1].k;
            if(s2a && s1n) g3 = h2a[1].k - h1n[1].k;
            if(s1b && s2a && s3n) g4 = h1b[1].k + h2a[1].k - h3n[1].k;

            if(g1>=g2 && g1>=g3 && g1>=g4){
                int k=h0[1].i, i=h1n[1].i, j=h2n[1].i;
                state[k]=3; state[i]=0; state[j]=0;
                sum += g1;
                popmax(h0,s0); popmin(h1n,s1n); popmin(h2n,s2n);
                pushmax(h0,s0,a[i]+b[i],i);
                pushmax(h0,s0,a[j]+b[j],j);
                pushmin(h3n,s3n,a[k]+b[k],k);
            } else if(g2>=g3 && g2>=g4){
                int k=h1b[1].i, j=h2n[1].i;
                state[k]=3; state[j]=0;
                sum += g2;
                popmax(h1b,s1b); popmin(h2n,s2n);
                pushmax(h0,s0,a[j]+b[j],j);
                pushmin(h3n,s3n,a[k]+b[k],k);
            } else if(g3>=g4){
                int k=h2a[1].i, i=h1n[1].i;
                state[k]=3; state[i]=0;
                sum += g3;
                popmax(h2a,s2a); popmin(h1n,s1n);
                pushmax(h0,s0,a[i]+b[i],i);
                pushmin(h3n,s3n,a[k]+b[k],k);
            } else {
                int i=h1b[1].i, j=h2a[1].i, k=h3n[1].i;
                state[i]=3; state[j]=3; state[k]=0;
                sum += g4;
                popmax(h1b,s1b); popmax(h2a,s2a); popmin(h3n,s3n);
                pushmin(h3n,s3n,a[i]+b[i],i);
                pushmin(h3n,s3n,a[j]+b[j],j);
                pushmax(h0,s0,a[k]+b[k],k);
            }
            overlap++;
        }
        putint(sum);
    }
    memcpy(d->stdout_ptr, obuf, optr);
    d->stdout_size = optr;
    __asm__ volatile("mov $60,%eax; xor %edi,%edi; syscall");
    __builtin_unreachable();
    return 0;
}

评测结果