Minimize Cost - HackerEarth Problem Solution

You are given an array of numbers

A_{i}

which contains positive as well as negative numbers . The cost of the array can be defined as

C (X)

C (x) = | A_{1} + T_{1} | + | A_{2} + T_{2} | + . . . . . . . . | A_{n} + T_{n} |

, where T is the transfer array which contains N zeros initially.

You need to minimize this cost . You can transfer value from one array element to another if and only if the distance between them is at most K.

Also, transfer value can't be transferred further.

Say array contains

3, - 1, - 2

and

K = 1

if we transfer 3 from

1^{s t}

element to

2^{n d}

, the array becomes

Original Value

3, - 1, - 2

Transferred value

- 3, 3, 0

C (x) = | 3 - 3 | + | - 1 + 3 | + . . . . . . . . | - 2 + 0 | = 4

which is minimum in this case

Input:

First-line contains N and K separated by space

Second-line denotes an array of size N

Output

Minimum value of C(X)

C (X)

Programsaddaa