MOJ Round #1Ended |
Para mejorar la salud de las embarazadas las autoridades de Cuba están planificando la construcción de una casa en la franja costera que tiene $N$ metros de largo. La franja costera está dividida en secciones, cada una con una longitud de un metro y están numeradas de izquierda a derecha, con números entre $1$ y $N$. Cada sección tiene una altitud representada por un entero no negativo. Los inversionistas desean que la casa esté ubicada ocupando $K$ secciones consecutivas de igual altura. Por supuesto, la región tiene desniveles por lo que ellos necesitan aplanar parte de la región de tal manera que puedan construir la casa. Para ello es necesario aumentar o disminuir la altura de algunas secciones. El costo de cada una de las dos operaciones es de una unidad.
Se desea hacer un programa que permita:
- Leer de la entrada estándar el largo de la franja costera, la cantidad de secciones que ocupará la casa y la altura de cada sección.
- Determinar el costo mínimo para aplanar las $K$ secciones y en cual sección se comenzará la construcción de la casa. Si hay más de una ubicación seleccione la que comience primero.
- Escribir hacia la salida estándar el costo mínimo para aplanar las $K$ secciones y la sección donde comenzará la construcción de la casa.
Línea 1 : dos enteros $N$ y $K$ separados entre sí por un espacio en blanco. El primero representa el largo de la franja costera y el segundo la cantidad de secciones que ocupará la casa de las embarazadas.
Línea 2 : aparecerán $N$ enteros separados entre sí por un espacio en blanco, los cuales representan la altura de cada sección.
Restricciones
- $5 \le N \le 10^6$.
- $3 \le K \le N$.
- La altitud de cada sección es menor o igual que $10^6$.
Línea 1
: En la primera línea se colocará el costo mínimo de aplanar las $K$ secciones para que queden a la misma altura.
Línea 2
: En la segunda línea aparecerá la sección a partir de la cual se construirá la casa de las embarazadas.