P1833 Cherry Blossoms

“The Story of Ai Yu Chou, Part 4 · plant”, Chapter 1.

Ai Yu Chou has planted $n$ cherry blossom trees in the backyard, each with an aesthetic value $C_i$ ($0 < C_i \le 200$). Every morning before school, Ai Yu Chou enjoys the blossoms. As a biology ace, he knows how to appreciate them: each tree can be viewed at most $P_i$ times, where $P_i = 0$ means unlimited views; otherwise, at most $P_i$ times. Viewing tree $i$ once takes $T_i$ minutes ($0 < T_i \le 100$). Only a short time remains before he must leave for school. Determine which trees to view (and how many times) to maximize the total aesthetic value while ensuring he can leave on time (or earlier).

There are $n+1$ lines. Line 1: current time $T_s$ (hour:minute), school departure time $T_e$ (hour:minute), and the number of trees $n$. The formats of $T_s$, $T_e$ are `hh:mm`, where $0 \le hh \le 23$, $0 \le mm \le 59$, and $n$ is a positive integer. Lines $2$ to $n+1$: three positive integers per line: the time to view tree $i$ once $T_i$, the aesthetic value of tree $i$ $C_i$, and the allowed view count $P_i$ ($P_i = 0$ means unlimited; otherwise, at most $P_i$ times).

Output a single integer, the maximum total aesthetic value.

Constraints: For $100\%$ of the testdata, $T_e - T_s \le 1000$ (i.e., the time from start to end does not exceed $1000$ minutes), and $n \le 10000$. It is guaranteed that $T_e$ and $T_s$ are within the same day. Sample explanation: view the first tree once, and the third tree $2$ times. Translated by ChatGPT 5