Bus and Passengers
Time limit2sMemory limit128 MB
Given up to 50000 requested one-directional bus segments and a bus of capacity C on a route of N stops, maximize the total number of passengers carried in one round trip without exceeding capacity at any point.
Problem
There is a bus route with N (1 <= N <= 10,000) stops. The stops are numbered 1, 2, ..., N in order. The bus starts at stop 1, travels to stop N, and then returns to stop 1 along the same route.
The bus company usually sends buses from stop 1 at regular intervals so that every customer can ride. Because heavy snow allows only one bus to run, the company must use survey data for K (1 <= K <= 50,000) requested travel sections.
The bus can carry at most C (1 <= C <= 100) people at once. During one round trip, the company wants to take as many customers as possible to their destinations. At each stop, the bus may drop off customers and pick up new ones. Once a customer boards, they cannot get off before reaching their destination.
Write a program that finds the maximum number of customers who can be carried to their destinations.
Input
The first line contains three integers K, N, and C. Each of the next K lines contains three integers S, E (1 <= S, E <= N), and M (1 <= M <= C), describing a requested bus section. S and E are different, and the line means that M customers want to travel from stop S to stop E.
Output
Print the maximum number of customers who can be carried to their destinations.
Hint
Carry two customers from stop 1 to stop 3. At stop 2, carry only one of the customers going to stop 8. Drop off the two customers at stop 3, then pick up one customer at stop 4 going to stop 7. Drop that customer off at stop 7, drop off the remaining customer at stop 8, and then pick up two customers going to stop 3. Drop those two customers off at stop 3 and return to stop 1.