Removiendo el Prado


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Después de ganar la competencia anual del pueblo para el mejor prado hace un año, el Granjero Juan se ha vuelto perezoso; no ha removido el prado desde entonces y por lo tanto su prado está descuidado. Sin embargo, pronto la competencia se va a volver a efectuar, y GJ quiere poner en forma su prado de tal manera que él pueda reclamar el titulo.

Desafortunadamente, GJ se ha dado cuenta que su prado está tan descuidado, que él necesitará la ayuda de algunas de sus N (1 \leq N \leq 100,000) vacas, las cuales están alineadas en una fila y numeradas convenientemente 1..N. Algunas vacas son más eficientes que otras moviendo el prado; la vaca i tiene eficiencia E_i  (0 \leq E_i \leq 1,000,000,000).

GJ se ha dado cuenta que frecuentemente las vacas vecinas en la fila frecuentemente se conocen bien entre ellas; también ha descubierto que si él elige más de K vacas (1 <= K <= N) vacas consecutivas (adyacentes) para que lo ayuden, ellas no le prestarán atención al prado y en vez de esto comenzaran una fiesta. Por lo tanto, GJ necesita que usted lo ayude: determine la mayor eficiencia total que GJ puede obtener sin elegir más de K vacas consecutivas.

Entrada

  • Línea 1: Dos enteros separados por espacio: N y K

  • Líneas 2..N+1: La línea i+1 contiene un solo entero: E_i

Ejemplo de Entrada

5 2
1
2
3
4
5

Detalles de la Entrada:

GJ tiene 5 vacas cuyas eficiencias son 1, 2, 3, 4, y 5, en ese orden. El quiere elegir algunas de las vacas de tal manera que su eficiencia total sea maximizada, pero él no puede elegir más de 2 vacas consecutivas.

Salida

  • Línea 1: Un solo entero que es la mejor eficiencia que GJ puede obtener.

Salida

12

Detalles de la Salida

GJ elige todas las vacas menos la tercera. La eficiencia total de las vacas es por lo tanto 1 + 2 + 4 + 5 = 12


Comments

There are no comments at the moment.