Cajas Mex

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 1G

Author:

eblabrada

Problem type

Allowed languages

C, C++, Python, Rust

Descripción

¡Finalmente Marco ha podido debutar en la Copa de la PlayStation Network (PSN) y ha conseguido llegar a la final! Como desafío Marco tiene $N$ ~N~ bolas, cada una con un número entero escrito en ella. Los números en las bolas son $a_1, a_2, \ldots, a_N$ ~a_1, a_2, \ldots, a_N~.

Ahora tiene que colocar estas $N$ ~N~ bolas en $K$ ~K~ cajas. Cada bola debe estar en alguna caja, pero puede haber cajas sin bolas o con múltiples bolas. Después de colocar las bolas en las cajas, la tapa de cada caja mostrará un número entero. Sea $x$ ~x~ el entero mostrado en una caja, $x$ ~x~ es el entero no negativo mínimo tal que la caja no contiene ninguna bola con $x$ ~x~. Por ejemplo, la tapa de una caja vacía mostrará $0$ ~0~; la tapa de una caja con bolas $0, 1, 3, 5$ ~0, 1, 3, 5~ mostrará $2$ ~2~; la tapa de una caja con bolas $1, 2, 3$ ~1, 2, 3~ mostrará $0$ ~0~.

Encuentra la suma máxima posible de los enteros mostrados en las tapas para que Marco logre ganar la final.

Entrada

La primera línea de la entrada contiene dos enteros $N$ ~N~ y $K$ ~K~ ( $1 \le K \le N \le 3 \times 10^5$ ~1 \le K \le N \le 3 \times 10^5~).

La segunda y última línea de la entrada contiene los valores $a_1, a_2, \ldots, a_N$ ~a_1, a_2, \ldots, a_N~ ( $0 \le a_i < N$ ~0 \le a_i < N~)

Salida

Imprime la suma máxima posible de los enteros mostrados en las tapas.

Ejemplos

Entrada 1

4 2
0 1 0 2

Salida 1

Una solución óptima es asignar los conjuntos de bolas $\{0,1,2\}, \{0\}$ ~\{0,1,2\}, \{0\}~ a las cajas.
En este caso, las tapas muestran $3,1$ ~3,1~, respectivamente, para un total de $4$ ~4~.

Entrada 2

5 2
0 1 1 2 3

Salida 2

Una solución óptima es asignar los (multi)conjuntos de bolas $\{0,1,1,2,3\}, \{\}$ ~\{0,1,1,2,3\}, \{\}~ a las cajas.
En este caso, las tapas muestran $4, 0$ ~4, 0~, respectivamente, para un total de $4$ ~4~.
Tenga en cuenta que podemos tener cajas vacías.

Entrada 3

20 4
6 2 6 8 4 5 5 8 4 1 7 8 0 3 6 1 1 8 3 0

Salida 3

Comments

-2

Jose_Ernesto commented on Dec. 19, 2023, 8:03 p.m.

Que alguien revise mi código

-2

Jose_Ernesto commented on Dec. 19, 2023, 8:03 p.m.

Ayudaa!!!