Maximum profit


In a game, you have the following:

  • Pile of N coins
  • List of restricted coins


  • A player can choose at most coins one by one.
  • They cannot choose a value that is present in the list of restricted coins.
  • At the beginning of the game, the list of restricted coins is empty. Whenever a player selects a coin, it is added to their profit and also appended in the list of restricted coins.
  • A player can discard a coin even if it is not present in the list of restricted coins.


Your task is to determine the maximum profit that a player can make.

Input format

  • The first line contains denoting the number of test cases.
  • In each test case:
    • The first line contains:
      • Two space-separated integers
      • Number of coins N
      • Maximum number of coins that a player can take K
    • The second line contains space-seperated integers denoting the value of the coins.

Output format

  • For each test case, print a single line denoting the maximum profit a player can make.


  • 1T20000

  • 1N200000

  • 1 <= Value of Coin <= 1e9
  • Sum of N over all test cases will not exceed 200000
Sample Input
5 4
2 3 3 2 2
Sample Output
Time Limit: 1
Memory Limit: 256
Source Limit:

Player can choose 2 and 3. He can not choose any number twice as it will be added to restricted coin list.

2 moves will be wasted as he has no other option so profit=2+3=5.


int main()
    long int n,k,t,i;
        long long int element,a[1000000]={0},sum=0,counter=0;
            if(a[element]==0 && counter<k )

    return 0;

Leave a Reply

Your email address will not be published.