Problem library

Squad Roles

Hard
bit masksdynamic programming

A squad has n players and n roles (at most 15). skill[p][r] is how well player p plays role r. Every player must take exactly one role and every role must be filled.

Return the largest possible total skill. The largest test has 15 players, so trying every assignment one by one is too slow.

Examples

Input: skill = [[7,3,1],[2,8,4],[6,5,9]]
Output: 24
Input: skill = [[5]]
Output: 5