← 返回题目列表

AtCoder · tkppc4_2_g

G. 平均评分

中文机器翻译题面 查看原题

配点: 700 点

問題文

除了部长 E869120 外,研究会还有 1 到 N 最多 N 人的成员。
研究会的成员都参加了 AtCoder 的比赛,E869120 目前的评分是 A、部員 i 的当前评分是 a_i 。
。 他为了让研究会变得更强,对除了自己的其他成员进行了如下操作若干次。

  • 操作 1: 部員 1 选择一个人进行教育。
    部員 i 该值应乘以 1 每进行一次教育,该成员的评分将 b_i 上涨。
    ,另外,如果多次教育同一成员,每次评分都会 b_i 上涨。
    。 此时,E869120 每次会消耗体力 c_i 。


  • 操作 2:从当前成员中选择 1 人施加压力让其退会。
    部員 i 当退会时,E869120 消耗体力 d_i 。

。 E869120 想在消耗的体力总和不超过 K 的情况下,通过这些操作,使包括他本人在内的研究会成员 AtCoder 评分的平均值达到最大化。
此时,请求出可以达到的最大平均评分。
此外,E869120 不能自我教育,也不能退出社团。

制約

  • 所有输入均为整数。
  • 1 \leq N \leq 1 \ 500
  • 1 \leq K \leq 1 \ 500
  • 1 \leq A \leq 10^9
  • 1 \leq a_i, b_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq c_i, d_i \leq K (1 \leq i \leq N)

小課題

这项作业需要 2 有两个子作业。
  1. (300 点) N, K \leq 500
  2. (400 分)没有其他限制。

入力

输入是按以下格式从标准输入给出的。

N K
A
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
...
a_N b_N c_N d_N

出力

请输出可以达到的最大平均等级。
如果绝对或相对误差为 如果在 10^{-4} 如果低于此值则为正确答案。


入力例1

3 200
2804
2416 20 30 80
2269 80 20 80
2115 30 40 70

出力例1

2656.33333

通过如下操作可以将平均等级最大化。

  • 首先,对社团成员施加压力,使其退出社团。 3 此时 E869120 的体力是 70 消耗。
  • 接下来,对部员进行教育。 2 该值应乘以 6 这时 E869120 君在体力 120 消耗。

操作之后,剩下的部员只有 E869120 君和部员, 1、部員 2 他们各自的评分为 2804、2416、2749 。


入力例2

2 170
1
30 1 10 50
20 30 50 50

出力例2

47.66667

请注意,E869120 君也可以教育比自己评分更高的部员。


入力例3

4 300
4089
2800 20 30 40
3200 30 40 50
3600 30 50 60
4000 20 70 80

出力例3

4089.00000

如果进行了最优操作,E869120 君可以让其他所有部员退部, 1 实验俱乐部的成员将只剩下 E869120 君一人。

作者: 秋鳗 通过重新排列获得的序列