Maximize Sum

shimul12614

National Girls' Programmi...

25/31/125

Statement Editorial Statistics Discussion

HTML

Limits 1s, 512 MB

You are given two integer arrays $A$ and $B$ of length $n$ and $m$ respectively. You can do the following operations on array $A$ .

Remove one element from $A$ . This operation can be performed at most $k$ times.
Insert any element of $B$ into $A$ at any position. You can insert each element of $B$ at most once.

Output the maximum possible value of $\displaystyle\sum_{i = 1}^{|A|} A_i \times i$ that you can achieve after performing the aforementioned operations.

Input

Input starts with an integer $T$ , denoting the number of test cases. In each test case,

The first line contains $3$ integers $n, m,$ and $k$ .

The second line contains $n$ integers $A_1, A_2, A_3, \ldots, A_n$ .

The third line contains $m$ integers $B_1, B_2, B_3, \ldots, B_m$ .

Constraints:

$1 \leq T \leq {10}^{4}$
$1\leq n \leq {10}^{4}$
$1 \leq m, k \leq 10$
$-{10}^{9} \leq A_i, B_i \leq {10}^{9}$

It is guaranteed that the sum of $n$ over all test cases does not exceed ${10}^{4}$ .

Output

For each test case, print the maximum possible value of $\displaystyle\sum_{i = 1}^{|A|} A_i \times i$ .

Samples

Input	Output
1 6 5 2 100 -10 20 -2000000 -5 500 -4 -5 -1 -2 70	6147
In the first test case, we shall perform the following operations: From array $A$ , remove $-2000000$ . After removing, array $A$ will become $[100, -10, 20, -5, 500]$ . From array $B$ , insert $-1$ at the beginning of array $A$ . After inserting, array $A$ will become $[-1, 100, -10, 20, -5, 500]$ . From array $B$ , insert $-2$ at the beginning of array $A$ . After inserting, array $A$ will become $[-2, -1, 100, -10, 20, -5, 500]$ . From array $B$ , insert $-4$ at the beginning of array $A$ . After inserting, array $A$ will become $[-4, -2, -1, 100, -10, 20, -5, 500]$ . From array $B$ , insert $-5$ at the beginning of array $A$ . After inserting, array $A$ will become $[-5, -4, -2, -1, 100, -10, 20, -5, 500]$ . From array $B$ , insert $70$ at the 8th position of array $A$ . After inserting, array $A$ will become $[-5, -4, -2, -1, 100, -10, 20, -5, 70, 500]$ . After completing those operations sequentially, array A gives the maximum result. $-5\times1 + -4\times2 + -2\times3 + -1\times4 + 100\times5 + -10\times6 + 20\times7 + -5\times8 + 70\times9 + 500\times10 = 6147$

Input

Output

1
6 5 2
100 -10 20 -2000000 -5 500
-4 -5 -1 -2 70

In the first test case, we shall perform the following operations:

From array $A$ , remove $-2000000$ . After removing, array $A$ will become $[100, -10, 20, -5, 500]$ .
From array $B$ , insert $-1$ at the beginning of array $A$ . After inserting, array $A$ will become $[-1, 100, -10, 20, -5, 500]$ .
From array $B$ , insert $-2$ at the beginning of array $A$ . After inserting, array $A$ will become $[-2, -1, 100, -10, 20, -5, 500]$ .
From array $B$ , insert $-4$ at the beginning of array $A$ . After inserting, array $A$ will become $[-4, -2, -1, 100, -10, 20, -5, 500]$ .
From array $B$ , insert $-5$ at the beginning of array $A$ . After inserting, array $A$ will become $[-5, -4, -2, -1, 100, -10, 20, -5, 500]$ .
From array $B$ , insert $70$ at the 8th position of array $A$ . After inserting, array $A$ will become $[-5, -4, -2, -1, 100, -10, 20, -5, 70, 500]$ .

After completing those operations sequentially, array A gives the maximum result.

$-5\times1 + -4\times2 + -2\times3 + -1\times4 + 100\times5 + -10\times6 + 20\times7 + -5\times8 + 70\times9 + 500\times10 = 6147$

Input	Output
5 4 1 1 -160 -290 -693 -597 38 2 2 3 -149 990 46 48 4 6 2 475 -164 -170 456 59 11 26 -45 -76 -65 6 4 4 997 -711 871 251 617 -306 84 -84 -20 -31 1 5 1 298 -98 -9 -1 -95 -87	-2379 4047 7160 17034 1198

Factors

	CPU	Memory	Source
Bash 5.2	1×	1×	1×
Brainf*ck	1×	1×	1×
C# Mono 6.0	1×	1×	1×
C++17 GCC 13.2	1×	1×	1×
C++20 Clang 16.0	1×	1×	1×
C++20 GCC 13.2	1×	1×	1×
C++23 GCC 13.2	1×	1×	1×
C11 GCC 13.2	1×	1×	1×
C17 GCC 13.2	1×	1×	1×
C23 GCC 13.2	1×	1×	1×
Common Lisp SBCL 2.0	1×	1×	1×
D8 11.8	1×	1×	1×
Erlang 22.3	1×	1×	1×
Free Pascal 3.0	1×	1×	1×
Go 1.22	1×	1×	1×
Grep 3.7	1×	1×	1×
Haskell 8.6	1×	1×	1×
Java 1.8	1×	1×	1×
Kotlin 1.1	1×	1×	1×
Lua 5.4	1×	1×	1×
Node.js 10.16	1×	1×	1×
Perl 5.30	1×	1×	1×
PHP 8.3	1×	1×	1×
PyPy 7.1 (3.6)	1×	1×	1×
Python 3.12	1×	1×	1×
Ruby 3.2	1×	1×	1×
Rust 1.57	1×	1×	1×
Swift 5.3	1×	1×	1×
Whitespace	1×	1×	1×

Submit

Statistics

81% Solution Ratio

ash_98Earliest, Feb '23

nusuBotFastest, 0.0s

chrootLightest, 15 MB

Fellow_juniorShortest, 917B