合格的签到题。
首先发现式子是一个 0-1 分数规划的模型,所以先二分答案 $mid$,男生 $i$ 和女生 $j$ 配对的价值为 $a_{i,j}-b_{i,j}\times mid$。
进一步地,发现男生和女生的关系形成一张二分图,并且男女双双配对,配对有权值,相当于二分图带权最大完美匹配。
可以使用 KM 算法求解,但我不会,学了一个费用流打了一下。核心思想就是把 EK 算法的 BFS 找增广路改为 SPFA 找增广路,顺便求一下最长路。
时间复杂度 $\mathcal O(n^4)$,在 COGS 的机器上可能有点难跑,但这只是理论上界,而且这可是二分图,SPFA 和 EK 都很难卡满,足以通过本题。