CF38C Blinds
题目描述
百叶窗通常由不透明的水平条带组成,这些条带可以旋转,从而调节进入房间的光线量。工厂仓库里有 $n$ 条宽度为 $1$ 的百叶窗条带。这些条带都是来自不同订单的备用零件,因此它们的长度可能不相同(甚至可以长度完全不同)。
每一条条带都可以被切割成两段或多段。切割是垂直于测量长度的那一边进行的,因此切割不会改变条带的宽度,但每段得到的条带长度变小(这些长度之和等于原始条带长度)。
所有切割完成后,百叶窗通过将若干长度相同的部分依次拼接在一起制成,拼接方式是沿着测量长度的那一边。不被切割的原始条带也可以直接作为百叶窗的一部分,但除此以外不能以其他方式构造百叶窗。
因此,如果百叶窗由 $k$ 段每段长度为 $d$ 的部分组成,它们将形成一个 $k×d$ bourlemeter 的矩形。
你的任务是计算:在技术允许的前提下(即不允许有长度小于 $l$ bourlemeter 的条带),从这些条带中制作百叶窗,能够覆盖的面积最大的矩形窗户的面积是多少。窗户的形状要求为长方形,两边长均为正整数。
输入格式
第一行包含两个用空格分隔的整数 $n$ 和 $l$($1 \leq n, l \leq 100$)。它们分别表示仓库中的条带数量和百叶窗条带可接受的最小长度(单位为 bourlemeter)。第二行包含 $n$ 个用空格分隔的整数 $a_i$,每个表示原始条带的长度($1 \leq a_i \leq 100$)。
输出格式
输出一个整数,表示能够完全覆盖的窗口最大面积(单位为平方 bourlemeter)。如果不存在可以完整覆盖的窗口(即无法满足所有要求),则输出 $0$。
说明/提示
在第一个样例中,所需的窗口尺寸为 $2×4$,每条百叶窗由 4 段、每段长度为 $2$ 的部分组成。其中一段是长度为 $2$ 的原始条带,另一段是长度为 $3$ 的百叶窗条带的一部分,另外两段是把长度为 $4$ 的条带切成两半后的部分。
由 ChatGPT 5 翻译