#PU650. USACO 2016 US Open Contest, Platinum — Problem 3. Landscaping
USACO 2016 US Open Contest, Platinum — Problem 3. Landscaping
USACO 2016 US Open Contest, Platinum — Problem 3. Landscaping
题目描述
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 flowerbeds (), where flowerbed initially contains units of dirt. Farmer John would like to re-landscape the garden so that each flowerbed instead contains units of dirt. The 's and 's are all integers in the range . 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 units of money. He can remove one unit of dirt from a flowerbed of his choice and have it shipped away for units of money. He can also transport one unit of dirt from flowerbed to flowerbed at a cost of times . Please compute the minimum total cost for Farmer John to complete his landscaping project.
输入格式
The first line of input contains , , , and (). Line contains the integers and .
输出格式
Please print the minimum total cost FJ needs to spend on landscaping.
数据范围
(见题面原文)
样例
样例 1
4 100 200 1
1 4
2 3
3 2
4 0
210
提示
at the silver level; however, the limits in the present version have been raised considerably, so one should not expect many points from the solution to the previous, easier version. Problem credits: Brian Dean