← All solutions

Shortest judge solution: 1142 bytes. Shortest team solution (during contest): 1431 bytes.

This is a classic max-flow/bipartite matching application. The transport schedule is defined by deciding, for each location 2 ≤ i ≤ n + 1, which location 1 ≤ j < i the catering team that serves request i comes from. In order for the schedule to be valid, it needs to satisfy two conditions:

• For the company location, node 1, at most k locations can select it as their predecessor location (reflecting that we only have k catering teams available).
• For each other location 2 ≤ j ≤ n + 1, at most one location i can choose j as their predecessor location.

In other words we have a bipartite graph with n vertices on the left side and n + 1 vertices on the right side, with an edge from node i on the left side to node j < i on the right side, with cost c_ji (the cost of transporting a catering set from location j to location i). An optimal transportation schedule is given by a minimum cost “matching” in this graph, where node 1 on the right side is allowed to be used up to k times (rather than at most once as in an actual matching).