GlobeX Cup '19 J4 - Winni's Lonely Card Game

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Winni is playing a card game with herself since she lost all of her friends when travelling to outer space. Winni lays N cards face up on the table. Each card has a non-unique number on it from 1 to M. Winni proceeds to pick up K cards from the table one at a time. Whenever Winni picks up a card, she receives O dollars where O is the number of cards with the same number that she has already picked up. Can you help Winni determine the maximum amount of money she can obtain?

Input Specification

The first line of input contains 3 integers, N, M, K.

The next line of input contains N integers between 1 to M, representing the number of the cards on the table.

Output Specification

Output the maximum amount of money she can obtain.


1 \le K \le N \le 10^5

1 \le M \le 10^9

Subtask 1 [10%]

N, M \le 10

Subtask 2 [20%]

N, M \le 10^3

Subtask 3 [30%]

M \le 10^5

Subtask 4 [40%]

No additional constraints.

Sample Input

7 10 5
10 8 9 10 9 9 10

Sample Output


Explanation For Sample

  1. She can initially pick up 10 gaining 0 dollars.
  2. She picks up 9, gaining 0 dollars.
  3. She then picks up 10, gaining 1 dollar.
  4. She picks up 10 again, gaining 2 dollars.
  5. She picks up 9 again, gaining 1 dollar.

In total, she gains 4 dollars, which is the maximum amount of money Winni can obtain.


There are no comments at the moment.