代码

// 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 raise the overlap by one at a time with one of four local moves, tracked
// by six hand-rolled binary heaps (max/min of a, b, a+b per state).
#include <sys/auxv.h>
#include <cstdio>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

typedef long long ll;
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], idx_[MAXN];

struct Node { ll k; int i; };
static Node h0[MAXN]; static int s0;
static Node h1n[MAXN]; static int s1n;
static Node h2n[MAXN]; static int s2n;
static Node h1b[MAXN]; static int s1b;
static Node h2a[MAXN]; static int s2a;
static Node h3n[MAXN]; static int s3n;

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 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;
}

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();
        int Kreq = (int)rd();
        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]; }
        }

        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);
        }

        const ll NEG = -(1LL << 62);
        while (overlap < Kreq) {
            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 = NEG, g2 = NEG, g3 = NEG, g4 = NEG;
            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;
        }
        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;
}

评测结果