JDCC '17 Contest 3 S4 - Interview Dominance

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Justin is feeling assertive, and decides to give his interviewer a programming challenge! Justin places N \(​(1 \le N \le 10^5)\) cards on the table, with each card having a certain number c_n (0 \le c_n \le 10^5) on it.

Every turn, Justin removes a single card from the table, and he gains a number of points equal to the number on the card.

Assume the number on the card picked is c​. Then, all cards with the number c + 1 and c - 1​ are removed from the table (Justin gets no points for these cards).

The game ends once there are no more cards on the table.

Justin asks the interviewer what the maximum number of points he can earn is, and not knowing the answer, the interviewer asks you to help them!


The first line contains an integer N \(​(1 \le N​ \le 10^5)\), representing the number of cards.

The next line has N​ integers c_n \((0 \le c​_n ​\le 10^5)\), representing the number on the \(n​^{th}\)​ ​card.

For 30\% of points, \(N​ \le 100\).


Output the maximum number of points that one can get by playing the game optimally.

This value may not fit in a 32-bit integer, and may need to be stored in a Long or long long variable in Java/C++ respectively (Python users are fine).

Sample Input

1 4 2 3 5 4 3

Sample Output


Explanation for Sample Input

Justin plays the following moves:

  • Remove the 5^{th} card (with value of 5) and remove all cards with a value of 4 or 6
  • Remove the 4^{th} card (with value of 3) and remove all cards with a value of 2 or 4
  • Remove the 1^{st} card (with value of 1) and remove all cards with a value of 0 or 2
  • Remove the 7^{th} card (with value of 3) and remove all cards with a value of 2 or 4

There are no more cards left and Justin ends up with 5 + 3 + 1 + 3 = 12 points in total.


There are no comments at the moment.