ZOJ Problem Set - 1567
The other day all the team members are having dinner together at a restaurant. As the restaurant is quite small, they've got few cooks and the waiting seems a bit endless. The good point is we know exact how long each dish will cost the restaurant to prepare, and also how long each dish will be finished. :P Let's define ta the time to prepare a dish, and tb the time to eat a dish, whereas s the satisfaction you get. Of course when there is no dish on the table, we get annoyed a lot and de-satisfy at a rate of d per second. Now given all the numbers, you are to find out the maximal satisfaction we can get out of this restaurant.
Notice you don't need to consider all the dishes since some might lessen your satisfaction.
Explanation of the sample
Author: CHEN, Gaoli
Source: ZOJ Monthly, March 2003