P5661 [CSP-J 2019] Public Transport Transfer

Famous tourist city B, in order to encourage everyone to travel by public transport, has introduced a discount plan for transferring from the subway to the bus: 1. After taking the subway once, you can obtain a discount ticket with a validity period of 45 minutes. Within the validity period, you may use this discount ticket to take one bus ride for free, as long as the bus fare does not exceed the subway fare. “Within the validity period” means that the difference between the start time of the bus ride and the start time of the subway ride is no more than 45 minutes, i.e. $t_{bus} - t_{subway} \leq 45$. 2. Discount tickets obtained from taking the subway can be accumulated, i.e. you can take the subway several times in a row and then use the discount tickets to take buses several times in a row. 3. When taking a bus, if a discount ticket can be used, it will definitely be used. If multiple discount tickets satisfy the conditions, the earliest obtained discount ticket will be used first. Now you have obtained Xiaoxuan’s recent public transport travel records. Can you help compute his total cost?

The first line of the input file contains a positive integer $n$, representing the number of travel records. The next $n$ lines each contain 3 integers, separated by a single space between adjacent numbers. In the $i$-th line, the first integer indicates the mode of transport for the $i$-th record: 0 represents subway, and 1 represents bus. The second integer indicates the fare for the $i$-th ride, $price_i$. The third integer indicates the start time of the $i$-th ride, $t_i$ (in minutes since time 0). It is guaranteed that the travel records are given in increasing order of start time, and no two ride records occur in the same minute.

The output file contains one line with a positive integer, representing Xiaoxuan’s total travel cost.

**Sample 1 Explanation** Record 1: At minute 3, pay 10 yuan to take the subway. Record 2: At minute 46, take the bus. You can use the discount ticket obtained from Record 1, so there is no cost. Record 3: At minute 50, pay 12 yuan to take the subway. Record 4: At minute 96, take the bus. Since it has been more than 45 minutes since the subway ride in Record 3, the discount ticket is no longer valid, so pay 3 yuan to take the bus. Record 5: At minute 110, pay 5 yuan to take the subway. Record 6: At minute 135, take the bus. At this time, only the discount ticket obtained from Record 5 is valid, but the bus fare is 6 yuan, which is higher than the subway fare 5 yuan from Record 5, so the discount ticket cannot be used. Pay 6 yuan to take the bus. The total cost is 36 yuan. **Sample 2 Explanation** Record 1: At minute 1, pay 5 yuan to take the subway. Record 2: At minute 16, pay 20 yuan to take the subway. Record 3: At minute 23, pay 7 yuan to take the subway. Record 4: At minute 31, take the bus. At this time, only the subway fare in Record 2 is higher than the bus fare for this ride, so use the discount ticket obtained from Record 2. Record 5: At minute 38, take the bus. At this time, both the discount tickets obtained from Record 1 and Record 3 can be used. Use the earliest obtained discount ticket, i.e. the one from Record 1. Record 6: At minute 68, take the bus. Use the discount ticket obtained from Record 3. The total cost is 32 yuan. **Constraints** For $30\%$ of the testdata, $n \leq 1000$, $t_i \leq 10^6$. For another $15\%$ of the testdata, $t_i \leq 10^7$, and all $price_i$ are equal. For another $15\%$ of the testdata, $t_i \leq 10^9$, and all $price_i$ are equal. For $100\%$ of the testdata, $n \leq 10^5$, $t_i \leq 10^9$, $1 \leq price_i \leq 1000$. Translated by ChatGPT 5