Tokens at the Fair
Submit solution
Points:
100 (partial)
Time limit:
2.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
C, C++
At a science fair in Puerto Rico, you play a game with n tokens, each marked with a positive integer. In one move, choose a token with value x: earn x points and remove that token. Also remove every remaining token with value x - 1 or x + 1. Other tokens with value x remain available.
You may make as many moves as you wish, including none. Find the maximum total score.
Input
The first line contains n. The second contains n integers a[1], a[2], …, a[n].
Output
Print one integer: the maximum total score. It may exceed the range of a signed 32-bit integer.
Constraints
1 ≤ n ≤ 100 000; 1 ≤ a[i] ≤ 100 000.
Execution limits
2 s · 256 MiB
Ejemplo
| Input Example | Output Example |
|---|---|
| 6 2 2 3 3 3 4 |
9 |
Choosing the three tokens with value 3 earns 9 points. Choosing values 2 and 4 earns only 8.
Source
Adapted for OiPR 2026. Codeforces 455A — Boredom.
Comments