代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef priority_queue<pair<int, int>> Heap;

template <typename C>
pair<int, int> gtop(C& q, C& dq) {
  while (!dq.empty() && dq.top() == q.top()) {
    dq.pop();
    q.pop();
  }
  if (q.empty())
    return make_pair(-1, -1);
  return q.top();
};

pair<int, int> neg(const pair<int, int>& pr) { return make_pair(-pr.first, pr.second); } 

void solve() {
  int n, k, l;
  scanf("%d%d%d", &n, &k, &l);
  vector<pair<int, int>> a(n), b(n), tot(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", &b[i]);
    b[i].second = i;
  }
  vector<int> vis(n);
  for (int i = 0; i < n; ++i)
    tot[i] = make_pair(a[i].first + b[i].first, i);
  if (k == l) {
    ll ans = 0;
    nth_element(tot.begin(), tot.begin() + k, tot.end(), greater<pair<int, int>>());
    for (int i = 0; i < k; ++i)
      ans += tot[i].first;
    printf("%lld\n", ans);
    return;
  }
  Heap qa(a.begin(), a.end()), dqa,
       qb(b.begin(), b.end()), dqb,
       qtot(tot.begin(), tot.end()), dqtot,
       qab, dqab, qba, dqba;
  Heap qda, dqda, qdb, dqdb;
  ll ans = 0;
  int ac = 0, bc = 0, ad = 0, bd = 0;
  for (int rep = 0; rep < k * 2; ++rep) {
    pair<int, int> opt(-1, -1);
    if (ad < k - l && ac < k) // 0 0 => 1 0
      opt = max(opt, make_pair(gtop(qa, dqa).first, 1));
    if (bd < k - l && bc < k) // 0 0 => 0 1
      opt = max(opt, make_pair(gtop(qb, dqb).first, 2));
    if (ad && bc < k) // [1 0] [0 0] => [0 0] [1 1]
      opt = max(opt, make_pair(gtop(qtot, dqtot).first + gtop(qda, dqda).first, 3));
    if (bd && ac < k) // [0 1] [0 0] => [0 0] [1 1]
      opt = max(opt, make_pair(gtop(qtot, dqtot).first + gtop(qdb, dqdb).first, 4));
    if (bc < k) // [1 0] => [1 1]
      opt = max(opt, make_pair(gtop(qab, dqab).first, 5));
    if (ac < k) // [0 1] => [1 1]
      opt = max(opt, make_pair(gtop(qba, dqba).first, 6));
    ans += opt.first;
    int pos, qos;
    switch (opt.second) {
    case 1:
      pos = gtop(qa, dqa).second; qa.pop();
      dqb.push(b[pos]);
      dqtot.push(tot[pos]);
      qab.push(b[pos]);
      qda.push(neg(a[pos]));
      ++ac; ++ad;
      break;
    case 2:
      pos = gtop(qb, dqb).second; qb.pop();
      dqa.push(a[pos]);
      dqtot.push(tot[pos]);
      qba.push(a[pos]);
      qdb.push(neg(b[pos]));
      ++bc; ++bc;
      break;
    case 3:
      pos = gtop(qtot, dqtot).second; qtot.pop();
      qos = gtop(qda, dqda).second; qda.pop();
      dqab.push(b[qos]);
      qb.push(b[qos]);
      qtot.push(tot[qos]);
      dqa.push(a[pos]);
      dqb.push(b[pos]);
      --ad; ++bc;
      break;
    case 4:
      pos = gtop(qtot, dqtot).second; qtot.pop();
      qos = gtop(qdb, dqdb).second; qdb.pop();
      dqba.push(a[qos]);
      qa.push(a[qos]);
      qtot.push(tot[qos]);
      dqa.push(a[pos]);
      dqb.push(b[pos]);
      --bd; ++ac;
      break;
    case 5:
      pos = gtop(qab, dqab).second; qab.pop();
      dqda.push(neg(a[pos]));
      ++bc;
      break;
    case 6:
      pos = gtop(qba, dqba).second; qba.pop();
      dqdb.push(neg(b[pos]));
      ++ac;
      break;
    }
  }
  printf("%lld\n", ans);
}

int main() {
#ifdef LBT
  freopen("sequence2.in", "r", stdin);
#endif

  int t;
  scanf("%d", &t);
  while (t--)
    solve();

  return 0;
}

评测结果