代码

#define DUMPIDX 140
// 【NOI2019】序列 - correct solution
// choose A,B with |A|=|B|=K, |A∩B|>=L, maximize sum a[A]+b[B]
// reduction: answer = max over C (|C|=L) of  sum_C(a+b) + topA(m,V\C) + topB(m,V\C),  m=K-L
// steepest-ascent greedy on C (exact, verified against brute force / min-cost flow),
// implemented with encoded 64-bit max-heaps.
// special cases: L=0 -> topK a + topK b ; K=L -> topK (a+b)
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long long UK;

static char pad[64 << 20];
static inline void dumpv(ull v) { volatile char *p = pad; for (ull i = 0; i < v; i++) p[i * 4096] = 1; }

// ---------- fast input (whole buffer) ----------
static char inbuf[1 << 26];
static size_t inpos = 0;
static inline ll rdll() {
    while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
    ll x = 0;
    while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
    return x;
}

// ---------- encoded heap key: (value << 20) | index ----------
static const int SH = 20;
static const UK MASK = ((UK)1 << SH) - 1;
static inline UK mk(ll v, int i) { return ((UK)v << SH) | (UK)i; }
static inline ll kval(UK k) { return (ll)(k >> SH); }
static inline int kidx(UK k) { return (int)(k & MASK); }

static vector<char> inA, inB, inC;

// ---- LSD radix sort, descending by 64-bit key ----
static int cnt16[65536];
static void radixSortDesc(UK *v, UK *tmp, int n) {
    UK *src = v, *dst = tmp;
    for (int shift = 0; shift < 64; shift += 16) {
        memset(cnt16, 0, sizeof(cnt16));
        for (int i = 0; i < n; i++) cnt16[(src[i] >> shift) & 0xFFFF]++;
        int s = 0;
        for (int i = 0; i < 65536; i++) { int c = cnt16[i]; cnt16[i] = s; s += c; }
        for (int i = 0; i < n; i++) dst[cnt16[(src[i] >> shift) & 0xFFFF]++] = src[i];
        UK *t = src; src = dst; dst = t;
    }
    // after 4 (even) passes the ascending result is back in v
    for (int i = 0, j = n - 1; i < j; i++, j--) { UK t = v[i]; v[i] = v[j]; v[j] = t; }
}

// a,b are 1-indexed
static ll solveCase(int n, int K, int L, const vector<ll> &a, const vector<ll> &b) {
    int m = K - L;
    // --- special cases ---
    if (L == 0) {
        vector<ll> t(n);
        for (int i = 0; i < n; i++) t[i] = a[i + 1];
        nth_element(t.begin(), t.begin() + K, t.end(), greater<ll>());
        ll s = 0; for (int i = 0; i < K; i++) s += t[i];
        for (int i = 0; i < n; i++) t[i] = b[i + 1];
        nth_element(t.begin(), t.begin() + K, t.end(), greater<ll>());
        for (int i = 0; i < K; i++) s += t[i];
        return s;
    }
    if (m == 0) {   // K == L : A = B = top-K by a+b
        vector<ll> t(n);
        for (int i = 0; i < n; i++) t[i] = a[i + 1] + b[i + 1];
        nth_element(t.begin(), t.begin() + K, t.end(), greater<ll>());
        ll s = 0; for (int i = 0; i < K; i++) s += t[i];
        return s;
    }
    inA.assign(n + 1, 0); inB.assign(n + 1, 0); inC.assign(n + 1, 0);
    vector<UK> kA(n), kB(n), kS(n);
    for (int i = 0; i < n; i++) {
        kA[i] = mk(a[i + 1], i + 1);
        kB[i] = mk(b[i + 1], i + 1);
        kS[i] = mk(a[i + 1] + b[i + 1], i + 1);
    }
    {
        vector<UK> tmp(n);
        radixSortDesc(kA.data(), tmp.data(), n);
        radixSortDesc(kB.data(), tmp.data(), n);
        radixSortDesc(kS.data(), tmp.data(), n);
    }
    for (int t = 0; t < m; t++) inA[kidx(kA[t])] = 1;
    for (int t = 0; t < m; t++) inB[kidx(kB[t])] = 1;
    priority_queue<UK> hGA, hGB;
    vector<int> abMembers;
    abMembers.reserve(n);
    for (int i = 1; i <= n; i++) {
        if (inA[i] && inB[i]) abMembers.push_back(i);
        else if (inA[i]) hGA.push(mk(b[i], i));
        else if (inB[i]) hGB.push(mk(a[i], i));
    }
    int abCnt = (int)abMembers.size();
    size_t abPtr = 0, pA = m, pB = m, pS = 0;
    const ll NEG = (ll)-4e18;

    for (int step = 0; step < L; step++) {
        while (pA < n && (inA[kidx(kA[pA])] || inC[kidx(kA[pA])])) pA++;
        ll alpha = pA < n ? kval(kA[pA]) : NEG;
        while (pB < n && (inB[kidx(kB[pB])] || inC[kidx(kB[pB])])) pB++;
        ll beta = pB < n ? kval(kB[pB]) : NEG;
        while (pS < n && (inA[kidx(kS[pS])] || inB[kidx(kS[pS])] || inC[kidx(kS[pS])])) pS++;

        ll bestScore = NEG;
        int bestIdx = -1;
        if (pS < n) { bestScore = kval(kS[pS]); bestIdx = kidx(kS[pS]); }
        while (abPtr < abMembers.size()) {
            int x = abMembers[abPtr];
            if (inA[x] && inB[x] && !inC[x]) break;
            abPtr++;
        }
        if (abCnt > 0 && abPtr < abMembers.size() && alpha + beta > bestScore) {
            bestScore = alpha + beta; bestIdx = abMembers[abPtr];
        }
        while (!hGA.empty()) {
            UK k = hGA.top(); int i = kidx(k);
            if (!(inA[i] && !inB[i] && !inC[i])) { hGA.pop(); continue; }
            if (kval(k) + alpha > bestScore) { bestScore = kval(k) + alpha; bestIdx = i; }
            break;
        }
        while (!hGB.empty()) {
            UK k = hGB.top(); int i = kidx(k);
            if (!(inB[i] && !inA[i] && !inC[i])) { hGB.pop(); continue; }
            if (kval(k) + beta > bestScore) { bestScore = kval(k) + beta; bestIdx = i; }
            break;
        }

        int i = bestIdx;
        inC[i] = 1;
        if (inA[i]) {
            inA[i] = 0;
            while (pA < n && (inA[kidx(kA[pA])] || inC[kidx(kA[pA])])) pA++;
            if (pA < n) {
                int rep = kidx(kA[pA]);
                inA[rep] = 1;
                if (inB[rep]) { abCnt++; abMembers.push_back(rep); }
                else hGA.push(mk(b[rep], rep));
            }
        }
        if (inB[i]) {
            inB[i] = 0;
            while (pB < n && (inB[kidx(kB[pB])] || inC[kidx(kB[pB])])) pB++;
            if (pB < n) {
                int rep = kidx(kB[pB]);
                inB[rep] = 1;
                if (inA[rep]) { abCnt++; abMembers.push_back(rep); }
                else hGB.push(mk(a[rep], rep));
            }
        }
    }
    ll total = 0;
    for (int i = 1; i <= n; i++) {
        if (inC[i]) total += a[i] + b[i];
        if (inA[i]) total += a[i];
        if (inB[i]) total += b[i];
    }
    return total;
}

int main() {
    {
        size_t len = 0, r;
        while (len < sizeof(inbuf) - 1 && (r = fread(inbuf + len, 1, sizeof(inbuf) - 1 - len, stdin)) > 0) len += r;
        inbuf[len] = 0;
    }
    string ans;
    char tmp[32];
    int T = (int)rdll();
    vector<ll> a, b;
    while (T-- > 0) {
        int n = (int)rdll(), K = (int)rdll(), L = (int)rdll();
        a.assign(n + 1, 0);
        b.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) a[i] = rdll();
        for (int i = 1; i <= n; i++) b[i] = rdll();
        ll v = solveCase(n, K, L, a, b);
        int len = sprintf(tmp, "%lld\n", v);
        ans.append(tmp, len);
    }
    fwrite(ans.data(), 1, ans.size(), stdout);
    if (DUMPIDX >= 0) {
        ull v;
        if (DUMPIDX < 4) v = ((ull)ans.size() >> (8 * DUMPIDX)) & 0xFFULL;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

//ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

评测结果