Loading...
Loading...
Loading...
A manager has N staff and N tasks. Staff i would cost C[i][j] to do task j. Every person gets exactly one task and every task is done by exactly one person. Print the smallest total cost.
Example
Input
3 9 2 7 6 4 3 5 8 1
Output
9
Person 0 takes task 1, person 1 task 0 and person 2 task 2: 2 + 6 + 1.
Try the problem first. Open one hint at a time.
Let dp[mask] be the cheapest way to give the first popcount(mask) people the tasks in mask.
From a mask, give the next person any task not in the mask. The answer is dp of the full mask.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor