Editorial for ICPC SWERC 2017 E - Ingredients
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
The solution combines shortest paths and 0/1 knapsack algorithms:
- the recipes form a DAG: compute first the topological sort of the recipe graph, and then compute in
time the dish costs;
- dynamic program for the knapsack problem in
, using the costs and prestiges.
Comments