#PU650. USACO 2016 US Open Contest, Platinum — Problem 3. Landscaping

    ID: 1577 传统题 文件IO:landscape 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open16来源:usaco.orgscoring:equal_test_cases

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 NN flowerbeds (1≤N≤100,0001 \leq N \leq 100,000), where flowerbed ii initially contains AiA_i units of dirt. Farmer John would like to re-landscape the garden so that each flowerbed ii instead contains BiB_i units of dirt. The AiA_i's and BiB_i's are all integers in the range 0…100 \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 XX units of money. He can remove one unit of dirt from a flowerbed of his choice and have it shipped away for YY units of money. He can also transport one unit of dirt from flowerbed ii to flowerbed jj at a cost of ZZ times ∣i−j∣|i-j|. Please compute the minimum total cost for Farmer John to complete his landscaping project.

输入格式

The first line of input contains NN, XX, YY, and ZZ (0≤X,Y≤108;0≤Z≤10000 \leq X, Y \le 10^8; 0 \le Z \leq 1000). Line i+1i+1 contains the integers AiA_i and BiB_i.

输出格式

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