|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #30Ended |
F - Array
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Probablemente estás cansado de largos y aburridos enunciados de problemas, por esa razón este tiene uno bastante simple.
Dado un array de $n$ enteros, debes seleccionar exactamente $k$ números en diferentes posiciones cuya suma sea mínima, pero esto no es todo, no pude haber dos elementos en posiciones consecutivas.
Input
La primera línea contiene dos enteros $n$ y $k$, $(1 \le n \le 100000, 1 \le k \le \frac{n+1}{2})$, indicando la longitud del array y la cantidad de posiciones a seleccionar. En la segunda línea aparecen $n$ enteros $a_i$ ($0 \le a_i \le 1000000000$) separados por espacio, indicando los valores en cada posición del array.
Output
En la primera línea imprima la menor suma posible que puede ser obtenida. Y en la segunda imprima $k$ enteros en orden creciente, siendo las posiciones que seleccionaste. De haber varias soluciones posibles, imprima cualquiera.
Sample test(s)
Input
4 2
6 2 1 2
Output
4
2 4