|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||4||0||0||0.000%|
Byteasar loved to play with building blocks as a child. He used to arrange the blocks into n columns of random height and then organize them in the following manner: Byteasar would choose a number k and try to arrange the blocks in such a way that some k consecutive columns would be of equal height. Furthermore he always tried to achieve this goal in a minimum number of moves possible, where a single move consists in:
However, Byteasar was never quite sure if his sequence of moves was indeed optimal, therefore he has asked you to write a programme that will help him solve the problem.
Write a programme that:
In the first line of the standard input there are two integers, n and k (1 ≤ k ≤ n ≤ 100,000), separated by a single space. Each of the following n lines contains the height of some column; the line no. i+1 contains the integer 0 ≤ hi ≤ 1,000,000 - the height of ith the column, ie. the number of blocks it consists of.
The optimal solution should be written out to the standard output, ie. such arrangement of blocks that:
The output should consist of n+1 lines, each one containing a single integer. The number in the first line should be the minimum number of moves needed to get the desired arrangement. The line no. i+1 (for 1 ≤ i ≤ n) should contain the number h'i - the final height of the ith column. If more than one optimal solution exists, write out one chosen arbitrarily.
5 3 3 9 2 3 1
2 3 9 2 2 2