Turismo

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Authors:

Marichal, leo

Problem type

Allowed languages

Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

Estás planeando un viaje para visitar N atracciones turísticas. Las atracciones están numeradas del 1 al N y deben ser visitadas en ese orden. Puedes visitar a la sumo K atracciones por día y deseas planificar el viaje tomando el menor número de días posible.

Bajo estas restricciones, usted desea encontrar un esquema que tenga un buen equilibrio entre las atracciones visitadas cada día. Para ser precisos, asignamos una puntuación $a_i$ ~a_i~ a la atracción i. Dado un esquema, cada día se da un puntaje igual al puntaje máximo de todas las atracciones visitadas ese día. Finalmente, las puntuaciones de cada día se suman para dar el puntaje total del esquema. ¿Cuál es el máximo total posible del esquema, usando el menor número de días posible?

Especificación de entrada

La primera línea contiene dos enteros separados por espacios N y K $(1 \leq K \leq N \leq 10^6)$ ~(1 \leq K \leq N \leq 10^6)~. La siguiente línea contiene N enteros separados por espacios $a_i (1 \leq a_i \leq 10^9)$ ~a_i (1 \leq a_i \leq 10^9)~.

Especificación de salida

Un simple entero, el máximo valor posible.

Ejemplo de entrada

5 3
2 5 7 1 4

Ejemplo de salida

Explicación:

Necesitamos al menos dos días para visitar las todas atracciones puesto que en un día no se pueden visitar todas. Visitando las dos primeras atracciones en el día 1 tendremos una puntuación de 5 y visitando las últimas tres atracciones el día 2 tendremos una puntuación de 7 para una puntuación total de 12.

Visitando las tres primeras atracciones el día 1 y las otras dos el día 2, lo cual es también posible en esta menor cantidad de días, nos da una puntuación de 7 + 4 = 11.

Comments

0

josue commented on March 21, 2020, 3:22 p.m.

gracias por la aclaracion

-1

josue commented on March 17, 2020, 2:47 p.m.

tomar el menor numero de días posibles quiere decir q va a existir n/k días q visita k atracciones y un día q visita n%k atracciones???

3

aniervs commented on March 21, 2020, 1:16 a.m.

No, significa que son $\lceil\frac{n}{k}\rceil$ ~\lceil\frac{n}{k}\rceil~ días. Por ejemplo, cuando $n=k+1$ ~n=k+1~, el primer día puede terminar en cualquier atracción $i\in[1,k]$ ~i\in[1,k]~, y entonces el segundo día empieza en $i+1$ ~i+1~; solo hay dos recorridos que cumplen lo que dices: cuando $i=k$ ~i=k~ y cuando $i=1$ ~i=1~, es posible que ninguno de ellos sea la solución óptima; por ejemplo: asumamos que $n=k+1$ ~n=k+1~ y que $n\ge 4$ ~n\ge 4~, y $a_1=a_n$ ~a_1=a_n~ son menores que todos los demás elementos del arreglo, entonces el recorrido $1—2$ para el primer día y $3—\dots —n$ para el segundo día es mayor que el recorrido $1$ ~1~ para el primer día y $2—\dots —n$ para el segundo día, y también es mayor que el recorrido $1—\dots—k$ para el primer día y $n$ ~n~ para el segundo día