P5902 [IOI 2009] Salesman

IOI 2009 D2T4.

The traveling salesman has found that the best overland travel plan is a hard computational problem to solve, so he moved his business to the linear world of the Danube River. He has a very fast boat that can take him from anywhere along the river to anywhere else in a short time, but unfortunately, this boat consumes a lot of fuel. The cost for the salesman to move upstream (toward the river source) by every meter is $U$ dollars, and the cost to move downstream (away from the river source) by every meter is $D$ dollars. There are $N$ fairs along the river that the salesman wants to attend. Each fair lasts only one day. For each fair $X$, the salesman knows its day $T_X$ (day $0$ is the day he bought the boat), the fair location $L_X$, and the profit $M_X$ he can earn at this fair. The location is the distance from the river source, in meters. He must **start and end** his trip at his home, located at position $S$. Help the salesman choose which fairs to attend (if any) and in what order, so that he can maximize his profit when the trip ends. The salesman’s total profit is the sum of dollars earned from attended fairs minus the dollars spent traveling upstream and downstream. Note that if fair $A$ is held earlier than fair $B$, then the salesman can only visit them in this order (i.e., he cannot visit fair $B$ first and then fair $A$). However, if two fairs are held on the same day, he may visit them in any order. There is no limit on how many fairs he can visit in one day, but he cannot earn profit from the same fair twice. He may pass through fairs he has already visited without earning anything. **Task**: Write a program that, given the day, location, and profit of each fair, as well as the location of the salesman’s home and his movement costs, computes the maximum profit he can have at the end of his trip.

The first line contains four integers $N, U, D, S$, separated by single spaces, representing the number of fairs, the per-meter cost of moving upstream ($U$) or downstream ($D$), and the position of the salesman’s home. The next $N$ lines describe the $N$ fairs. The $k$-th line contains three integers, separated by single spaces, representing the fair day $T_k$, its location $L_k$, and the profit $M_k$ the salesman can earn at this fair.

Output one integer: the maximum profit the salesman can have at the end of the trip.

### Sample Explanation In one optimal plan, the salesman attends fairs $1$ and $3$ (at positions $80$ and $75$, respectively). The sequence of events and the corresponding profit are as follows: - The salesman leaves home and moves upstream by $20$ meters, costing $100$ dollars. Current profit: $-100$. - The salesman attends fair $1$ and earns $100$ dollars. Current profit: $0$. - The salesman moves upstream by $5$ meters, costing $25$ dollars. Current profit: $-25$. - The salesman attends fair $3$ and earns $150$ dollars. Current profit: $125$. - The salesman moves downstream by $25$ meters to return home, costing $75$ dollars. Final profit: $50$. ### Constraints - For $60\%$ of the testdata, no two fairs are held on the same day. - For $40\%$ of the testdata, all input numbers are at most $5000$. - $15\%$ of the testdata satisfies both conditions above, and $85\%$ satisfies at least one of them. - For $100\%$ of the testdata, $1 \le N, T_k \le 5\times 10^5$, $1 \le D \le U \le 10$, $1 \le S, L_k \le 5 \times 10^5 +1$, $1 \le M_k \le 4000$. Translated by ChatGPT 5