#P17990. House

House

House

题目描述

有 nn 根木材,长度分别为 a1,…,ana_1,\ldots,a_n。你想建造底面为 x×yx\times y 的矩形房屋,四面墙各需叠放 kk 块木板,因此总共需要 2k2k 块长度为 xx 的木板和 2k2k 块长度为 yy 的木板。

木板长度可以是正实数。每根长度为 aia_i 的木材可以切成任意若干块,只要这些木板的长度总和不超过 aia_i。可以留下余料,但不能把不同木材拼接起来。

求能够建造的房屋的最大底面积 xyxy。

输入格式

第一行两个整数 n,kn,k。第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出一个实数,表示最大面积。设精确答案为 RR,输出为 SS,必须满足

∣S−R∣≤10−9max⁡(1,R).|S-R|\le10^{-9}\max(1,R).

小数点后最多输出 2020 位数字。

数据范围

1≤n≤10001\le n\le1000,1≤k≤301\le k\le30,1≤ai≤10001\le a_i\le1000。

样例 1 输入

1 5
10

样例 1 输出

0.25

将唯一的木材切成 2020 块长度为 0.50.5 的木板。

样例 2 输入

5 1
6 7 1 3 2

样例 2 输出

12

可以建造 6×26\times2 或 4×34\times3 的房屋。

样例 3 输入

5 7
1 4 5 7 5

样例 3 输出

0.602

最优尺寸为 0.7×0.860.7\times0.86。