代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

const ll INF = 1E18;
const int maxl = 35, maxr = 155, maxn = 2000005;
ll dp[maxl][maxl][maxl][maxl], a[maxn], b[maxn];
int n, k, lim;
void cmax(ll &a, ll b) { a = max(a, b); }
void getdp() {
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= k; j++)
			for (int l = 0; l <= k - j; l++)
				for (int r = 0; r <= k - j; r++) {
					if (j + 1 <= k) cmax(dp[i + 1][j + 1][l][r], dp[i][j][l][r] + a[i + 1] + b[i + 1]);
					if (l + 1 <= k - j) cmax(dp[i + 1][j][l + 1][r], dp[i][j][l][r] + a[i + 1]);
					if (r + 1 <= k - j) cmax(dp[i + 1][j][l][r + 1], dp[i][j][l][r] + b[i + 1]);
					cmax(dp[i + 1][j][l][r], dp[i][j][l][r]);
				}
	ll ans = 0;
	for (int i = lim; i <= k; i++) cmax(ans, dp[n][i][k - i][k - i]);
	printf("%lld\n", ans);
}
const int maxs = 100005;
int nn = 1E9;
struct Set {
	ll sum[maxs];
	int cnt[maxs], ls[maxs], rs[maxs], tcnt;
	inline void clear() {
		for (register int i = 1; i <= tcnt; i++) ls[i] = rs[i] = sum[i] = cnt[i] = 0; 
		tcnt = 1;
	}
	inline void modify(int a, int b, int l = 1, int r = nn, int k = 1) {
		if (l == r) {
			cnt[k] += b;
			sum[k] += a * b;
			return;
		}
		int mid = l + r >> 1;
		if (a <= mid) {
			if (!ls[k]) ls[k] = ++tcnt;
			modify(a, b, l, mid, ls[k]);	
		} else {
			if (!rs[k]) rs[k] = ++tcnt;
			modify(a, b, mid + 1, r, rs[k]); 
		}
		sum[k] = sum[ls[k]] + sum[rs[k]];
		cnt[k] = cnt[ls[k]] + cnt[rs[k]];
	} 
	inline ll query(int tk, int l = 1, int r = nn, int k = 1) {
		if (l == r) return (ll)l * min(cnt[k], tk);
		int mid = l + r >> 1;
		if (cnt[rs[k]] >= tk) return query(tk, mid + 1, r, rs[k]);
		return query(tk - cnt[rs[k]], l, mid, ls[k]) + sum[rs[k]];
	}
} S1, S2;
int id[maxr], len;
ll pa[maxr], pb[maxr], res = 0;
inline ll calc() { return res + S1.query(len) + S2.query(len); }
void rands() {
	ll curf, ans = -INF;
	len = k - lim;
	for (register int i = 1; i <= n; i++) id[i] = i;
	for (register int temp = 1; temp <= 10; temp++) {
		if (temp % 4 == 1) {
			random_shuffle(id + 1, id + n + 1);
			S1.clear(), S2.clear(), res = 0;
			for (int i = 1; i <= lim; i++) res += a[id[i]] + b[id[i]];
			for (int i = lim + 1; i <= n; i++)
				S1.modify(a[id[i]], 1), S2.modify(b[id[i]], 1);
			curf = calc();
		}
		for (register int i = 1; i <= lim; i++)
			for (register int j = lim + 1; j <= n; j++) {
				res = res - a[id[i]] - b[id[i]] + a[id[j]] + b[id[j]]; 
				S1.modify(a[id[j]], -1), S2.modify(b[id[j]], -1);
				S1.modify(a[id[i]], 1), S2.modify(b[id[i]], 1);
				swap(id[i], id[j]);
				ll newf = calc();
				if (newf > curf) curf = newf;
				else {
					res = res - a[id[i]] - b[id[i]] + a[id[j]] + b[id[j]]; 
					S1.modify(a[id[j]], -1), S2.modify(b[id[j]], -1);
					S1.modify(a[id[i]], 1), S2.modify(b[id[i]], 1);
					swap(id[i], id[j]);
				}
			}
		ans = max(ans, curf);
	}
	printf("%lld\n", ans);
}
P c[maxn];
bool used[maxn];
ll ta[maxn], tb[maxn];
void greedy() {
	memset(used, 0, sizeof(used));
	for (int i = 1; i <= n; i++) {
		c[i].first = a[i] + b[i];
		c[i].second = i;
	}
	sort(c + 1, c + n + 1), reverse(c + 1, c + n + 1);
	ll ans = 0;
	for (int i = 1; i <= lim; i++)
		ans += c[i].first, used[c[i].second] = 1;
	int t = 0;
	for (int i = 1; i <= n; i++)
		if (!used[i])
			ta[++t] = a[i], tb[t] = b[i]; 
	sort(ta + 1, ta + t + 1), sort(tb + 1, tb + t + 1);
	reverse(ta + 1, ta + t + 1), reverse(tb + 1, tb + t + 1);
	for (int i = 1; i <= k - lim; i++) ans += ta[i] + tb[i];
	printf("%lld\n", ans);
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &k, &lim);
		for (register int i = 1; i <= n; i++) scanf("%lld", a + i);
		for (register int i = 1; i <= n; i++) scanf("%lld", b + i);
		if (n <= 30) getdp();
		else if (n <= 150) rands();
		else greedy();
	}
	return 0;
}

评测结果