代码

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int __buffsize = 100000;
char __buff[__buffsize];
char *__buffs, *__buffe;

#define getc() (__buffs == __buffe ? fread(__buff, 1, __buffsize, stdin), __buffe = __buff + __buffsize, *((__buffs = __buff)++) : *(__buffs++))

template<typename T> inline T &Read(T &x)
{
	static char c;
	while (1) 
	{ 
		c = getc(); 
		if (c == '-' || (c >= '0' && c <= '9')) break; 
	}
	bool flag = c == '-';
	x = flag ? 0 : c - '0';
	while (1)
	{
		c = getc();
		if (c < '0' || c > '9') break;
		(x *= 10) += c - '0';
	}
	if (flag) x = -x;
	return x;
}

#undef getc

const int maxn = 200100;

int n, K, L;
int a[maxn + 5], b[maxn + 5];
int pos[maxn + 5];
int rk[maxn + 5];
int posa[maxn + 5], posb[maxn + 5];
int rka[maxn + 5], rkb[maxn + 5];

LL ans = 0;

bool ina[maxn + 5], inb[maxn + 5];

struct cmpa
{
	bool operator()(int x, int y) { return a[x] > a[y]; }
};

struct icmpa
{
	bool operator()(int x, int y) { return a[x] < a[y]; }
};

struct cmpb
{
	bool operator()(int x, int y) { return b[x] > b[y]; }
};

struct icmpb
{
	bool operator()(int x, int y) { return b[x] < b[y]; }
};

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int T;
	Read(T);
	while (T--)
	{
		Read(n), Read(K), Read(L);
		REP(i, 0, n) Read(a[i]);
		REP(i, 0, n) Read(b[i]);
		REP(i, 0, n) pos[i] = posa[i] = posb[i] = i;
		sort(pos, pos + n, [&](int x, int y) { return a[x] + b[x] > a[y] + b[y]; });
		sort(posa, posa + n, [&](int x, int y) { return a[x] > a[y]; });
		sort(posb, posb + n, [&](int x, int y) { return b[x] > b[y]; });
		REP(i, 0, n) rk[pos[i]] = i, rka[posa[i]] = i, rkb[posb[i]] = i;

		priority_queue<int, vector<int>, cmpa> a0, a1;
		priority_queue<int, vector<int>, icmpa> a2;
		priority_queue<int, vector<int>, cmpb> b0, b1;
		priority_queue<int, vector<int>, icmpb> b2;

		LL cur = 0;
		REP(i, 0, L) cur += a[pos[i]] + b[pos[i]], a0.push(pos[i]), b0.push(pos[i]);

		{
			int res = K - L;
			REP(i, 0, n) 
				if (res && rk[posa[i]] >= L)
				{
					--res;
					cur += a[posa[i]];
					ina[posa[i]] = 1;
					a1.push(posa[i]);
				}
				else a2.push(posa[i]);
		}

		{
			int res = K - L;
			REP(i, 0, n) 
				if (res && rk[posb[i]] >= L)
				{
					--res;
					cur += b[posb[i]];
					inb[posb[i]] = 1;
					b1.push(posb[i]);
				}
				else b2.push(posb[i]);
		}

		ans = 0;
		chkmax(ans, cur);
		REP(i, L, min(n, 2 * K - L))
		{
			bool needa = 0, needb = 0;
			if (ina[pos[i]]) ina[pos[i]] = 0, cur -= a[pos[i]];
			else needa = 1;
			if (inb[pos[i]]) inb[pos[i]] = 0, cur -= b[pos[i]];
			else needb = 1;
			cur += a[pos[i]] + b[pos[i]];
			a0.push(pos[i]);
			b0.push(pos[i]);
			while (!a1.empty() && rk[a1.top()] <= i) a1.pop();
			while (!b1.empty() && rk[b1.top()] <= i) b1.pop();
			while (!a2.empty() && rk[a2.top()] <= i) a2.pop();
			while (!b2.empty() && rk[b2.top()] <= i) b2.pop();
			if (needa && needb)
			{
				if (a1.empty() && b1.empty()) break;
				int tmpa = INT_MAX, tmpb = INT_MAX;
				if (!a1.empty()) tmpa = a[a1.top()] + b[b0.top()];
				if (!b1.empty()) tmpb = b[b1.top()] + a[a0.top()];
				if (tmpa < tmpb)
				{
					cur -= tmpa;
					ina[a1.top()] = 0;
					a2.push(a1.top());
					a1.pop(), b0.pop();
				}
				else
				{
					cur -= tmpb;
					inb[b1.top()] = 0;
					b2.push(b1.top());
					b1.pop(), a0.pop();
				}
			}
			else if (needa || needb)
			{
				int tmpa = INT_MAX, tmpb = INT_MAX;
				if (needa) tmpa = a[a0.top()];
				else if (!b1.empty() && !a2.empty()) tmpa = a[a0.top()] + b[b1.top()] - a[a2.top()];
				if (needb) tmpb = b[b0.top()];
				else if (!a1.empty() && !b2.empty()) tmpb = b[b0.top()] + a[a1.top()] - b[b2.top()];
				if (tmpa == INT_MAX && tmpb == INT_MAX) break;
				if (tmpa < tmpb)
				{
					cur -= tmpa;
					a0.pop();
					if (!needa) 
					{
						inb[b1.top()] = 0;
						b2.push(b1.top());
						b1.pop();
						a1.push(a2.top());
						ina[a2.top()] = 1;
						a2.pop();
					}
				}
				else
				{
					cur -= tmpb;
					b0.pop();
					if (!needb) 
					{
						ina[a1.top()] = 0;
						a2.push(a1.top());
						a1.pop();
						b1.push(b2.top());
						inb[b2.top()] = 1;
						b2.pop();
					}
				}
			}
			else
			{
				int tmpa = INT_MAX, tmpb = INT_MAX;
				if (!a2.empty()) tmpa = a[a0.top()] - a[a2.top()];
				if (!b2.empty()) tmpb = b[b0.top()] - b[b2.top()];
				if (tmpa == INT_MAX && tmpb == INT_MAX) break;
				if (tmpa < tmpb)
				{
					cur -= tmpa;
					a0.pop();
					a1.push(a2.top());
					ina[a2.top()] = 1;
					a2.pop();
				}
				else
				{
					cur -= tmpb;
					b0.pop();
					b1.push(b2.top());
					inb[b2.top()] = 1;
					b2.pop();
				}

			}
			chkmax(ans, cur);
		}

		cout << ans << endl;
	}
	return 0;
}

评测结果