Cửa hàng bán hoa

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

SK mở hai cửa hàng bán hoa và nhập hoa từ ~N~ vườn. Mỗi vườn có ~A_i~ bông hoa với tổng giá trị là ~C_i~. SK sẽ mua hết số hoa trong ~N~ vườn và đưa đến hai cửa hàng của mình. Hoa của một vườn chỉ có thể đưa đến một cửa hàng duy nhất.

Với giá hoa trung bình tại cửa hàng 1 là ~P_1~, giá hoa trung bình tại cửa hàng hai là ~P_2~ và giá hoa trung bình trong mỗi cửa hàng được tính bằng tổng giá trị hoa chia cho số bông hoa có trong cửa hàng đó, SK muốn phân chia hoa về các cửa hàng sao cho tích ~P_1 \times P_2~ là nhỏ nhất có thể.

Yêu cầu: Giúp SK phân chia hoa về hai cửa hàng sao cho ~P_1 \times P_2~ là nhỏ nhất có thể, với chú ý sau khi phân chia hoa về các cửa hàng thì phải có ít nhất một cửa hàng nhận hoa từ ~L~ vườn.

Dữ liệu

  • Dòng 1 gồm hai số nguyên ~N~ và ~L~ (~2 ≤ N ≤ 100,1 ≤ L < N~) – số bông hoa và số hoa trong ít nhất một cửa hàng.
  • Dòng 2 gồm ~N~ số nguyên ~A_i (1 ≤ A_i ≤ 100)~, tổng các số nguyên ~A_i ≤ 500~.
  • Dòng 3 gồm ~N~ số nguyên ~C_i (1 ≤ C_i ≤ 1000000)~.

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Kết quả

  • Ghi ra một số thực duy nhất là tích ~P_1 \times P_2~ nhỏ nhất có thể (làm tròn tới ba chữ số phần thập phân).

Input

3 1
3 2 1
1 2 3

Output

0.556

Input

3 2
2 2 2
3 3 3

Output

2.250

Ràng buộc: 30% số điểm tương ứng với 30% số test có N≤20.


Nguồn: DHBB 2017 (HP)


Be the first to comment

Comments

There are no comments at the moment.