Double Beauty | Practice Problems

Double Beauty

★★★★★

3 votes

Greedy Algorithms, Basics of Greedy Algorithms, Sorting, Algorithms, Merge Sort

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ of length $N$ . You can select $K$ distinct indexes and double the element in them.

The beauty of the array is the sum of any subarray of length $K$ . Find the maximum beauty over all permutations of array $A$ .

Input Format:

The first line contains an integer $T$ , denoting the number of test cases.
The first line of each test case contains two integers $N$ and $K$ respectively.
The second line of each test case contains $N$ space-separated integers, denoting the elements of the array.

Output Format:

For each test case, print the maximum beauty over all permutations of $A$ .

Constraints:

$1 <= T <= 10$

$1 <= K <= N <= 10^5$

$1 <= A[i] <= 10^3$

Sample Input

Sample Output

16
10

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

First test case:
We can select indexes $2$ , $3$ , and $4$ (1-based indexing).
$A$ becomes $[1, 8, 2, 6, 1]$ . The permutation that gives maximum beauty is $[1, 8, 2, 6, 1]$ . Hence, the answer is $16$ .

Second test case:
We can select index $2$ (1-based indexing).
$A$ becomes $[2, 10, 1]$ . The permutation that gives maximum beauty is $[2, 10, 1]$ . Hence, the answer is $10$ .

Contributers:

Rohit Pradhan

Geetartha Kaustav