Los Tablones de la Valla


Submit solution

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

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

Hay una cerca frente a la casa de David. La valla consta de n tablones del mismo ancho que van uno tras otro de izquierda a derecha. La altura del i-ésimo tablón es h_i metros; tablones distintos pueden tener alturas distintas.

Descripción

David ha comprado un piano elegante y está pensando en cómo meterlo en la casa. Para llevar a cabo su plan, necesita tomar exactamente k tablones consecutivos de la cerca. Los tablones más altos son más difíciles de arrancar de la valla, por lo que David quiere encontrar k tablones consecutivos que la suma de sus alturas sea la mínima posible.

Escriba un programa que encuentre los índices de k tablones consecutivos con altura total mínima. Atención, la cerca no está alrededor de la casa de David, está frente a la casa (en otras palabras, la cerca no es cíclica).

Entrada

La primera línea de la entrada contiene los números enteros n y k (1 \leq n \leq 1.5*10^5, 1 \leq k \leq n) – el número de tablones en la cerca y el ancho del agujero para el piano. La segunda línea contiene la secuencia de números enteros h_1, h_2,..., h_n (1 \leq h_i \leq 100), donde h_i es la altura de la i-ésima tabla de la cerca.

Salida

Imprima tal entero j que la suma de las alturas de los tablones j, j+1,..., j+k-1 sea la mínima posible. Si hay varias j de este tipo, imprima la menor.

Ejemplo de Entrada

7 3
1 2 6 1 1 7 1

Ejemplo de Salida

3

Explicación

En la muestra, su tarea es encontrar tres tablones consecutivos con la suma mínima de alturas. En el caso dado, los tres tablones con índices 3, 4 y 5 tienen el atributo requerido, su altura total es 8.


Comments


  • 3
    Marco_Escandon  commented on Jan. 14, 2024, 5:05 a.m.

    Por favor no usen los comentarios del dmoj. Usen chats de whatsapp, telegram, discord o lo que usen.

    Lean el siguiente enlace: https://dmoj.uclv.edu.cu/tos/:

    Usar los comentarios exclusivamente para intercambiar sobre los problemas, competencias o posts del blog. Nos reservamos el derecho de eliminar sin previo aviso cualquier comentario que incumpla esta condición.

    Usar un lenguaje cordial y respetuoso para dirigirse a los demás usuarios y administradores.

    Los usuarios que realicen comentarios irrespetuosos u obscenos perderán su derecho a comentar de forma permanente.

    No atentar deliberadamente contra el correcto funcionamiento del juez en línea.


    • 2
      JoJo_Cubano_13  commented on Jan. 15, 2024, 2:39 a.m.

      Pido disculpas por cualquier problema ocasionado, puesto que todo fue producto de una tarde de aburrimiento. Independientemente de todo eso, no tengo excusa, simplemente pido disculpas, y prometo que no se volverá a repetir. Muchas gracias por su atención y una vez más disculpen por las molestias y problemas ocasionados.


  • 0
    aledaniel  commented on Oct. 1, 2023, 7:32 p.m.

    Lo hago en python y en c++ lo más optimizado posible y siempre da error de tiempo, saqué 79 en python y 80 en c++