NOI '19 P3 - Sequence

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given two positive integer sequences \left\{a_{1}, a_{2}, \cdots, a_{n}\right\} and \left\{b_{1}, b_{2}, \cdots, b_{n}\right\} of length n, you must find two sequences \left\{c_{1}, c_{2}, \cdots, c_{K}\right\} and \left\{d_{1}, d_{2}, \cdots, d_{K}\right\} of length K satisfying the following conditions:

  1. 1 \leq c_{1}<c_{2}<\cdots<c_{K} \leq n.
  2. 1 \leq d_{1}<d_{2}<\cdots<d_{K} \leq n.
  3. \left|\left\{c_{1}, c_{2}, \cdots, c_{K}\right\} \cap\left\{d_{1}, d_{2}, \cdots, d_{K}\right\}\right| \geq L.

Subject to these conditions, maximize \sum_{i=1}^{K} a_{c_{i}}+\sum_{i=1}^{K} b_{d_{i}}.

Input Specification

The first line contains an integer T, indicating the number of testcases.

For each testcase:

The first line contains three integers n,K,L.

The second line contains n integers, indicating \left\{a_{1}, a_{2}, \cdots, a_{n}\right\}.

The third line contains n integers, indicating \left\{b_{1}, b_{2}, \cdots, b_{n}\right\}.

Constraints

For all test cases, 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.

Test Casen \le\sum n \le
1~3103\times 10^5
4~518
6~730
8~10150
11~162\,000
17~212\times 10^5
22~2510^6

Output Specification

Output one integer on one line, the answer.

Sample Input 1

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

Sample Output 1

14
12
27
45
62

Comments

There are no comments at the moment.