题目描述
参加聚餐的鸟人有 N 只雄性和 N 只雌性。雄性 i 与雌性 j 的亲和度为非负整数 ai,j。你可以为每只鸟人分别支付任意非负实数,支付多少,它就获得多少快乐。
你也可以在音乐设备上花费任意非负实数 S。如果音乐设备的价格是 C,每对异性鸟人所需的快乐总和会降低 S/C。也就是说,若雄性 i 和雌性 j 的快乐分别为 xi,yj,则必须满足
xi+yj+CS≥ai,j.
每个询问独立给出一个价格 C。求满足所有要求的最小总花费 S+∑ixi+∑jyj。
输入格式
第一行一个整数 Num,表示测试点编号。
第二行两个整数 N,Q,分别表示每类鸟人的数量和询问数。
接下来 N 行,每行 N 个整数,第 i 行第 j 个数为 ai,j。
接下来 Q 行,每行一个整数 C。
输出格式
每个询问输出一行一个实数,保留一位小数。保证精确答案的小数点后第二位不是 4 或 5。
样例输入 1
1
1 1
5
1
样例输出 1
5.0
样例输入 2
2
3 3
3 0 0
4 5 0
0 4 3
1
2
5
样例输出 2
5.0
8.0
11.0
数据范围与约定
对于所有数据,1≤N≤500,1≤Q≤5000,0≤ai,j≤109,1≤C≤109。
| 子任务 |
分值 |
N |
Q |
特殊性质 |
| 1 |
3 |
=1 |
≤5 |
无 |
| 2 |
15 |
≤5 |
ai,j,C≤5 |
| 3 |
22 |
≤50 |
=1 |
C=109 |
| 4 |
25 |
≤50 |
无 |
| 5 |
12 |
≤200 |
≤5000 |
| 6 |
23 |
≤500 |
原 PDF 题面