Farmer John is building a nicely-landscaped garden, and needs to move a large amount of dirt in the process.

The garden consists of a sequence of N flowerbeds (1 \leq N \leq 100,000), where flowerbed i initially contains A_iunits of dirt. Farmer John would like to re-landscape the garden so that each flowerbed i instead contains B_i units of dirt. The A_i's and B_i's are all integers in the range 0 \ldots 10.

To landscape the garden, Farmer John has several options: he can purchase one unit of dirt and place it in a flowerbed of his choice for X units of money. He can remove one unit of dirt from a flowerbed of his choice and have it shipped away for Y units of money. He can also transport one unit of dirt from flowerbed i to flowerbed j at a cost of Z times |i-j|. Please compute the minimum total cost for Farmer John to complete his landscaping project.

Problem credits: Brian Dean

#3631 upload 4 done 3 how_to_reg 3

Landscaping timer 2s memory 512MB

#3631

Landscaping 2s 512MB