仓库建设

提交数: 2, 通过率: 100%, 平均分: 100

题目描述:

1514355483959139973.png

输入格式:

第一行包含一个整数N，表示工厂的个数。接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。

输出格式:

仅包含一个整数，为可以找到最优方案的费用。

样例输入:

3
0 5 10
5 3 100
9 6 10

样例输出:

32

提示:

【样例说明】

       在工厂1和工厂3建立仓库，建立费用为10+10=20，运输费用为(9-5)*3 = 12，总费用32。

       如果仅在工厂3建立仓库，建立费用为10，运输费用为(9-0)*5+(9-5)*3=57，总费用67，不如前者优。

【数据规模】

对于20%的数据，   N ≤500；

对于40%的数据，   N ≤10000；

对于100%的数据， N ≤1000000。

所有的Xi, Pi, Ci均在32位带符号整数以内，保证中间计算结果不超过64位带符号整数。

时间限制: 3000ms
空间限制: 256MB

来源: 浙江省选2007day2t4