P3161 [CQOI2012] Simulated Factory

There is a game called “Simulated Factory” as follows: at time $0$, the factory’s productivity equals $1$. At each time, you may either increase productivity or produce goods. If you choose to increase productivity, then at the next time the factory’s productivity increases by $1$; if you choose to produce goods, then at the next time your number of goods increases by $p$, where $p$ is the factory’s productivity at the current time. There are $n$ orders, and you may choose to accept or reject each one. The $i$-th order $(t_i, g_i, m_i)$ requires delivering $g_i$ goods to the buyer at time $t_i$. After completion, your goods decrease by $g_i$, and your revenue increases by $m_i$ yuan. If you accept order $i$, you must transact exactly at time $t_i$, neither earlier nor later. Multiple orders may be accepted at the same time, but each order can be accepted at most once. Maximize the final total revenue. For example, if there are two orders $(5,1,8)$ and $(7,15,3)$, the following strategy is optimal: at times $0$, $1$, $2$ increase productivity (so the productivity at time $3$ is $4$), then at times $3$ and $4$ produce goods; at time $5$ you will have $8$ goods. Accept order $1$ at this time (you will still have $7$ goods left), and continue producing goods at times $5$ and $6$; then at time $7$ you will have $7+4+4=15$ goods, exactly meeting order $2$.

The first line contains an integer $n$, the number of orders. Each of the following $n$ lines contains three integers $t_i, g_i, m_i$.

Output a single line with the maximum total revenue. The answer is guaranteed to fit in the 32-bit signed integer range.

Constraints | Index | $n \le$ | $t_i \le$ | $g_i \le$ | $m_i \le$ | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 3$ | $5$ | $100$ | $10000$ | $10000$ | | $4 \sim 6$ | $10$ | $100$ | $10000$ | $10000$ | | $7 \sim 10$ | $15$ | $100000$ | $10^9$ | $10^9$ | Translated by ChatGPT 5