代码

// This code is AI-generated. (AI 生成的代码)
// NOI2019 序列: pick two size-L index sets with at least K common indices,
// maximising sum a[A] + b[B].  Start from the L largest a and the L largest b,
// then repeatedly raise the overlap by one with one of four local moves tracked
// by six heaps (max/min of a, b, a+b grouped by each element's state).
#include <sys/auxv.h>
#include <cstdio>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>

typedef long long ll;
using std::pair;
using std::vector;
using std::make_pair;
using std::priority_queue;
using std::greater;
using std::nth_element;

struct DuckInfo {
    uint64_t abi; 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;
} __attribute__((packed));

enum { MAXN = 200005 };
static ll a[MAXN], b[MAXN];
static int state_[MAXN];
static int idx_[MAXN];
static const char *sp;
static inline ll rd() {
    while (*sp < '0' || *sp > '9') ++sp;
    ll v = 0;
    while (*sp >= '0' && *sp <= '9') v = v * 10 + (*sp++ - '0');
    return v;
}

typedef priority_queue<pair<ll, int> > MaxHeap;
typedef priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > MinHeap;

static inline void cleanMax(MaxHeap &h, int st) { while (!h.empty() && state_[h.top().second] != st) h.pop(); }
static inline void cleanMin(MinHeap &h, int st) { while (!h.empty() && state_[h.top().second] != st) h.pop(); }

int main() {
    struct DuckInfo *d = (struct DuckInfo *)getauxval(0x6b637564UL);
    static char local_in[1 << 24], local_out[1 << 22];
    char *obuf;
    int is_judge = 0;
    if (d && d->stdin_ptr) { sp = d->stdin_ptr; obuf = d->stdout_ptr; is_judge = 1; }
    else { size_t z = fread(local_in, 1, sizeof(local_in), stdin); local_in[z] = 0; sp = local_in; obuf = local_out; }

    int T = (int)rd();
    char *o = obuf;
    while (T--) {
        int n = (int)rd();
        int Lset = (int)rd();   // size of A and B
        int Kreq = (int)rd();   // required overlap
        for (int i = 0; i < n; ++i) a[i] = rd();
        for (int i = 0; i < n; ++i) b[i] = rd();
        for (int i = 0; i < n; ++i) state_[i] = 0;

        for (int i = 0; i < n; ++i) idx_[i] = i;
        nth_element(idx_, idx_ + Lset, idx_ + n, [](int x, int y) { return a[x] > a[y]; });
        ll sum = 0;
        for (int t = 0; t < Lset; ++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_ + Lset, idx_ + n, [](int x, int y) { return b[x] > b[y]; });
        int overlap = 0;
        for (int t = 0; t < Lset; ++t) {
            int i = idx_[t];
            if (state_[i] == 1) { state_[i] = 3; ++overlap; sum += b[i]; }
            else { state_[i] = 2; sum += b[i]; }
        }

        MaxHeap h0;
        MinHeap h1n, h2n, h3n;
        MaxHeap h1b, h2a;
        for (int i = 0; i < n; ++i) {
            if (state_[i] == 0) h0.push(make_pair(a[i] + b[i], i));
            else if (state_[i] == 1) { h1n.push(make_pair(a[i], i)); h1b.push(make_pair(b[i], i)); }
            else if (state_[i] == 2) { h2n.push(make_pair(b[i], i)); h2a.push(make_pair(a[i], i)); }
            else h3n.push(make_pair(a[i] + b[i], i));
        }

        const ll NEG = -(1LL << 62);
        while (overlap < Kreq) {
            cleanMax(h0, 0); cleanMin(h1n, 1); cleanMin(h2n, 2);
            cleanMax(h1b, 1); cleanMax(h2a, 2); cleanMin(h3n, 3);
            ll g1 = NEG, g2 = NEG, g3 = NEG, g4 = NEG;
            if (!h0.empty() && !h1n.empty() && !h2n.empty()) g1 = h0.top().first - h1n.top().first - h2n.top().first;
            if (!h1b.empty() && !h2n.empty()) g2 = h1b.top().first - h2n.top().first;
            if (!h2a.empty() && !h1n.empty()) g3 = h2a.top().first - h1n.top().first;
            if (!h1b.empty() && !h2a.empty() && !h3n.empty()) g4 = h1b.top().first + h2a.top().first - h3n.top().first;

            if (g1 >= g2 && g1 >= g3 && g1 >= g4) {
                int k = h0.top().second, i = h1n.top().second, j = h2n.top().second;
                state_[k] = 3; state_[i] = 0; state_[j] = 0; sum += g1;
                h0.pop(); h1n.pop(); h2n.pop();
                h0.push(make_pair(a[i] + b[i], i));
                h0.push(make_pair(a[j] + b[j], j));
                h3n.push(make_pair(a[k] + b[k], k));
            } else if (g2 >= g3 && g2 >= g4) {
                int k = h1b.top().second, j = h2n.top().second;
                state_[k] = 3; state_[j] = 0; sum += g2;
                h1b.pop(); h2n.pop();
                h0.push(make_pair(a[j] + b[j], j));
                h3n.push(make_pair(a[k] + b[k], k));
            } else if (g3 >= g4) {
                int k = h2a.top().second, i = h1n.top().second;
                state_[k] = 3; state_[i] = 0; sum += g3;
                h2a.pop(); h1n.pop();
                h0.push(make_pair(a[i] + b[i], i));
                h3n.push(make_pair(a[k] + b[k], k));
            } else {
                int i = h1b.top().second, j = h2a.top().second, k = h3n.top().second;
                state_[i] = 3; state_[j] = 3; state_[k] = 0; sum += g4;
                h1b.pop(); h2a.pop(); h3n.pop();
                h3n.push(make_pair(a[i] + b[i], i));
                h3n.push(make_pair(a[j] + b[j], j));
                h0.push(make_pair(a[k] + b[k], k));
            }
            ++overlap;
        }
        // write sum
        if (sum < 0) { *o++ = '-'; sum = -sum; }
        char t[24]; int k = 0;
        if (!sum) t[k++] = '0';
        while (sum) { t[k++] = (char)('0' + sum % 10); sum /= 10; }
        while (k) *o++ = t[--k];
        *o++ = '\n';
    }
    if (is_judge) {
        d->stdout_size = (uint64_t)(o - obuf);
        __asm__ volatile("mov $60, %%eax; xor %%edi, %%edi; syscall" ::: "rax", "rdi", "memory");
        __builtin_unreachable();
    }
#ifdef LOCAL
    fwrite(obuf, 1, o - obuf, stdout);
#endif
    return 0;
}

评测结果