P3529 [POI 2011] PRO-Programming Contest

Bartie and his friends compete in the Team Programming Contest. There are $n$ contestants on each team, and each team has access to $n$ computers. The contest lasts $t$ minutes, during which the contestants are to solve $m$ programming problems. Furthermore, penalties are imposed on the teams: solving a problem $s$ minutes since the beginning of the contest amounts to $s$ penal points. The team that solved the most problems wins the contest, with ties broken in favour of the team with smaller penalty. On the contest day Bartie quickly glances over the problem statements and distributes them among his teammates. He knows his team so well that he can exactly assess who is able to solve which problem. Solving any problem takes any contestant that is able to solve it exactly $r$ minutes of using the computer. Bartie's team did not fare well in this year's contest. Bartie is obsessed with the thought that it might be his fault, due to wrong decisions regarding the distribution of problems. He asks you to write a program that, given what Bartie knew at the beginning of the contest, determines the best possible result of Bytie's team, together with the assignment of problems to team members that attains the result.

N/A

N/A