All Tracks>Algorithms> Greedy Algorithms> Basics of Greedy Algorithms> Problem
Double Beauty
★★★★★

5

3 votes
Greedy Algorithms, Basics of Greedy Algorithms, Sorting, Algorithms, Merge Sort
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<=105

1<=A[i]<=103

Sample Input
2
5 3
1 4 1 3 1
3 1
2 5 1
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:
Editor Image

?