【NOI2019】序列 - 题目 - Universal Online Judge

给定两个长度为 $n$ 的正整数序列 ${a_{i}}$ 与 ${b_{i}}$ ，序列的下标为 $1, 2, \dots, n$ 。现在你需要分别对两个序列各指定恰好 $K$ 个下标，要求至少有 $L$ 个下标在两个序列中都被指定，使得这 $2 K$ 个下标在序列中对应的元素的总和最大。

形式化地说，你需要确定两个长度为 $K$ 的序列 ${c_{i}}, {d_{i}}$ ，其中

$1 \leq c_{1} < c_{2} < \dots < c_{K} \leq n, 1 \leq d_{1} < d_{2} < \dots < d_{K} \leq n$

并要求

$| {c_{1}, c_{2}, \dots, c_{K}} \cap {d_{1}, d_{2}, \dots, d_{K}} | \geq L$

目标是最大化

$\sum_{i = 1}^{K} a_{c_{i}} + \sum_{i = 1}^{K} b_{d_{i}}$

输入格式

从标准输入中读入数据。

本题输入文件包含多组数据。

第一行一个正整数 $T$ 表示数据组数。接下来每三行表示一组数据。

每组数据第一行三个整数 $n, K, L$ ，变量意义见题目描述。

每组数据第二行 $n$ 个整数表示序列 ${a_{i}}$ 。

每组数据第三行 $n$ 个整数表示序列 ${b_{i}}$ 。

输出格式

输出到标准输出中。

对于每组数据输出一行一个整数表示答案。

样例一

input

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

output

explanation

第一组数据选择的下标为： ${c_{i}} = {1}, {d_{i}} = {1}$ ；

第二组数据选择的下标为： ${c_{i}} = {1, 3}, {d_{i}} = {2, 3}$ ；

第三组数据选择的下标为： ${c_{i}} = {3, 4}, {d_{i}} = {3, 5}$ ；

第四组数据选择的下标为： ${c_{i}} = {2, 3, 4, 6}, {d_{i}} = {2, 3, 4, 6}$ ；

第五组数据选择的下标为： ${c_{i}} = {2, 3, 4, 5, 6}, {d_{i}} = {1, 2, 3, 4, 6}$ 。

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

对于所有测试数据： $T \leq 10, 1 \leq \sum n \leq 10^{6}, 1 \leq L \leq K \leq n \leq 2 \times 10^{5}, 1 \leq a_{i}, b_{i} \leq 10^{9}$ 。

每个测试点的具体限制见下表：

测试点编号	$n \leq$	$\sum n$
$1 \sim 3$	$10$	$3 \times 10^{5}$
$4, 5$	$18$
$6, 7$	$30$
$8 \sim 10$	$150$
$11 \sim 16$	$2 \times 10^{3}$
$17 \sim 21$	$2 \times 10^{5}$
$22 \sim 25$	$2 \times 10^{5}$	$10^{6}$

时间限制： $1 s$

空间限制： $512 MB$

下载

样例数据下载

Universal Online Judge

UOJ

#480. 【NOI2019】序列