OI题库

题目3  老师的工资

 

【问题描述】

    不只是学生会在功课上偷懒，有时候老师也是一样的。对部分老师来说，如果不能够拿到足够的工资，他们的工作便不如被期望的那样努力。Fengzee给学校的校长提了一个建议，就是用合理的工资分配来使老师们工作的积极性达到最高。校长作为决策者，要考虑整个学校的m个老师，同时还要明白每年他只能在老师的工资上总共付出n万元钱（满足m,n为整数，且m）。每个老师一年得到的钱都是整万元，如果认为给某个老师发工资比较亏本，校长可以决定辞退这名老师，同时不必支付任何金钱。在某些极端情况下，甚至可以把n万元钱全部给1名老师。经过一段时间的观察，校长发现，每一个老师在每一种工资数额下，工作的积极性是不同的。现在校长要求这个建议的提出者Fengzee写一个程序，来求出在一年中校长全部利用且只利用这n万元钱的情况下，老师们最佳的总积极性。总积极性被认为是每个老师的工作积极性的和。

    Fengzee当然会写这个简单的程序，可是为了帮助你参加信息学竞赛，他想让你来练习一下。你的输入文件由两部分组成：第一部分有一行，用空格分隔，依次提供m和n这两个整数；第二部分是一个m*n的矩阵，假设用a表示，那么矩阵中的元素a[i][j]的值是第i个老师在拿到j万元的年薪时的工作积极性，用一个整数表示，整数的规模不会很大。值得注意的是，对有些老师来说，拿过多的钱会增长惰性，使他们的工作积极性反而不如低工资的时候高。输出文件只有一行，包含一个整数p，表示最佳分配方案下的总积极性。答案正确并不超过时限是获得测试数据全部得分的充分必要条件。

 

【数据规模】

1<=m<=15, 2<=n<=30

 

【输入样例】teacher.in

5 10

30 40 60 80 100 110 120 100 90 80

20 50 80 100 120 130 133 134 135 136

20 60 70 90 140 160 180 190 210 220

30 50 70 90 110 130 150 170 190 210

40 55 100 130 135 140 145 150 155 160

 

【输出样例】teacher.out

300