题目描述
给定两个长度为 n 的正整数序列 {ai} 与 {bi},序列的下标为 1,2,…,n。现在你需要分别对两个序列各指定恰好 K 个下标,要求至少有 L 个下标在两个序列中都被指定,使得这 2K 个下标在序列中对应的元素的总和最大。
形式化地说,你需要确定两个长度为 K 的序列 {ci},{di},其中
1≤c1<c2<…<cK≤n,1≤d1<d2<…<dK≤n
并要求
{c1,c2,…,cK}∩{d1,d2,…,dK}≥L
目标是最大化
i=1∑Kaci+i=1∑Kbdi
输入格式
从文件 sequence.in
中读入数据。
本题输入文件包含多组数据。
第一行一个正整数 T 表示数据组数。接下来每三行表示一组数据。
每组数据第一行三个整数 n,K,L,变量意义见题目描述。
每组数据第二行 n 个整数表示序列 {ai}。
每组数据第三行 n 个整数表示序列 {bi}。
输出格式
输出到文件 sequence.out
中。
对于每组数据输出一行一个整数表示答案。
样例
5
1 1 1
7
7
3 2 1
4 1 2
1 4 2
5 2 1
4 5 5 8 4
2 1 7 2 7
6 4 1
1 5 8 3 2 4
2 6 9 3 1 7
7 5 4
1 6 6 6 5 9 1
9 5 3 9 1 4 2
14
12
27
45
62
第一组数据选择的下标为: {ci}={1},{di}={1};
第二组数据选择的下标为: {ci}={1,3},{di}={2,3};
第三组数据选择的下标为: {ci}={3,4},{di}={3,5};
第四组数据选择的下标为: {ci}={2,3,4,6},{di}={2,3,4,6};
第五组数据选择的下标为: {ci}={2,3,4,5,6},{di}={1,2,3,4,6}。
见选手目录下的 sequence/sequence2.in
与 sequence/sequence2.ans
。
见选手目录下的 sequence/sequence3.in
与 sequence/sequence3.ans
。
数据范围与提示
对于所有测试点:T≤10,1≤∑n≤106,1≤L≤K≤n≤2×105,1≤ai,bi≤109。
每个测试点的具体限制见下表:
测试点编号 |
n≤ |
∑n≤ |
1∼3 |
10 |
3×105 |
4,5 |
18 |
6,7 |
30 |
8∼10 |
150 |
11∼16 |
2×103 |
17∼21 |
2×105 |
22∼25 |
106 |