Art Academy II: The Grand Escape

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 64M

PyPy 2 128M

Author:

BenZeng

Problem type

After being trapped and tormented inside of hewmatt10's ~~basement~~ "Art Academy", astrocat879 decided that it was finally time for him to plan an escape. Fortunately, hewmatt10 had never actually considered the possibility of him wanting to escape, so the actual escape would be a piece of cake.

Along the Academy, there are a total of $N$ ~N~ paintings spread across the area, each with a value of $v_i$ ~v_i~. Since astrocat879 is short on money, he plans to steal some of the paintings while making his escape. However, because hewmatt10 is insecure, all of his paintings' values have been hashed, meaning that the value that astrocat879 sees them at is NOT the actual value. Specifically, the paintings' values have been hashed using the following function:

$hash(i)=i\space\times\space2654435761\mod 2^{32}$

( $hash(i)$ ~hash(i)~ represents the hashed value, while $i$ ~i~ represents the original value. It is guaranteed that all integer values of $i$ ~i~ under $2^{32}$ ~2^{32}~ will be given a unique hash value.)

astrocat879 doesn't have the time to figure out the original value of the paintings, and so has asked YOU to create a program for him, that will to maximize his profits. More specifically, he would like you to sum up the $M$ ~M~ paintings with the greatest original value.

Input Specification

On the first line, there will be two space-separated integers, $N$ ~N~, and $M$ ~M~. $($ ~(~ $1$ ~1~ $\le$ ~\le~ $M$ ~M~ $\le$ ~\le~ $N$ ~N~ $\le$ ~\le~ $3 \times 10^5$ ~3 \times 10^5~ $)$ ~)~ The next $N$ ~N~ lines will contain a single integer $v_i$ ~v_i~, representing the hashed value of the $ith$ ~ith~ painting. It is guaranteed that the original value of this hashed number will be greater than $0$ ~0~, but no greater than $2^{31}$ ~2^{31}~.

Output Specification

A single integer, representing the sum of the $M$ ~M~ paintings with the greatest original value.

Subtasks

Subtask	Points	Description
1	10	$1$ ~1~ $\le$ ~\le~ $N$ ~N~ $\le$ ~\le~ $10^2$ ~10^2~, $i$ ~i~ $\le$ ~\le~ $2^{16}$ ~2^{16}~.
2	10	$1$ ~1~ $\le$ ~\le~ $N$ ~N~ $\le$ ~\le~ $10^2$ ~10^2~.
3	80	No further constraints.

Sample Input

Sample Output

Explanation

The original values for the paintings with values $387276917$ ~387276917~, $145972072$ ~145972072~, $2654435761$ ~2654435761~, $147926525$ ~147926525~, and $2415085369$ ~2415085369~, are $5$ ~5~, $1000$ ~1000~, $1$ ~1~, $13$ ~13~, and $9$ ~9~, respectively.

The sum of the two greatest values, $1000$ ~1000~ and $13$ ~13~, is $1013$ ~1013~.

Comments

There are no comments at the moment.