P2120 [ZJOI2007] Warehouse Construction

Company L has $n$ factories distributed from high to low along a mountain; factory $1$ is at the summit, and factory $n$ is at the foot. Because the mountain is in an inland plateau region (dry with little rain), Company L usually stacks products directly in the open air to save costs. One day, Mr. L, the president of Company L, received a call from the meteorological department and was informed that there would be a heavy rain in three days. Therefore, Mr. L decided to urgently build some warehouses at certain factories to prevent the products from getting wet. Due to differences in terrain, the cost of building a warehouse may vary from one factory to another. Factory $i$ currently has $p_i$ finished items, and the cost of building a warehouse at factory $i$ is $c_i$. For factories where no warehouse is built, their products should be transported to other warehouses for storage. Since Company L’s external sales outlet is located at factory $n$ at the foot of the mountain, products can only be transported downhill (that is, **only to the warehouse of a factory with a larger index**). Of course, transportation also costs money: transporting one item over one unit of distance costs $1$. Assume that any warehouse built is large enough to hold all products. You will be given the following data: - The distance from factory $i$ to factory $1$, $x_i$ (where $x_1 = 0$). - The current number of finished items at factory $i$, $p_i$. - The cost of building a warehouse at factory $i$, $c_i$. Please help Company L find a warehouse construction plan that minimizes the total cost (construction cost + transportation cost).

The first line contains an integer $n$, the number of factories. Lines $2$ through $(n + 1)$ each contain three space-separated integers. On line $(i + 1)$, the integers are $x_i,~p_i,~c_i$ in order.

Output a single line with one integer, the cost of the optimal plan.

#### Explanation for Sample Input/Output $1$ Build warehouses at factory $1$ and factory $3$. The construction cost is $10 + 10 = 20$, the transportation cost is $(9 - 5) \times 3 = 12$, and the total cost is $32$. #### Constraints and Agreements - For $20\%$ of the testdata, it is guaranteed that $n \leq 500$. - For $40\%$ of the testdata, it is guaranteed that $n \leq 10^4$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^6$, $0 \leq x_i,p_i,c_i < 2^{31}$. - For any $1 \leq i < n$, it is guaranteed that $x_i < x_{i + 1}$. - Let the answer be $ans$, and it is guaranteed that $ans + \sum\limits_{i = 1}^{n} p_ix_i < 2^{63}$. Translated by ChatGPT 5