CF924E Wardrobe

Olya 想要购买一个定制衣柜。这个衣柜应该有 $n$ 个盒子，每个盒子的高度分别为 $a_{1},a_{2},...,a_{n}$，这些盒子可以以任意顺序上下堆叠。换句话说，我们可以将每个盒子表示为一个长度为 $a_{i}$ 的竖直线段，所有这些线段应当首尾相接，形成一个从 $0$ 到总高度的连续线段，且不能有重叠。 其中有些盒子是重要的（即 $b_{i}=1$），其余则不是（$b_{i}=0$）。Olya 定义衣柜的“便利度”为：底边高度在 $l$ 到 $r$（包含 $l$ 和 $r$）之间的所有重要盒子的数量。 你得到了每个盒子的高度和重要性的信息。请计算，如果可以任意重新排列盒子的顺序，衣柜的最大便利度是多少。

第一行包含三个整数 $n$、$l$ 和 $r$（$1 \leq n \leq 10000$，$0 \leq l \leq r \leq 10000$），分别表示盒子的数量、重要盒子的底边高度计入便利度的最低和最高高度。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 10000$），表示每个盒子的高度。保证所有盒子的高度之和（即衣柜的总高度）不超过 $10000$：Olya 个子不高，够不到更高的地方。 第三行包含 $n$ 个整数 $b_{1},b_{2},...,b_{n}$（$0 \leq b_{i} \leq 1$），其中 $b_{i}=1$ 表示第 $i$ 个盒子是重要的，$b_{i}=0$ 表示不重要。

输出一个整数，表示衣柜的最大便利度。

在第一个样例中，你可以先放一个高度为 $2$ 的不重要盒子，然后依次放高度为 $1$、$3$ 和 $2$ 的重要盒子，最后放剩下的不重要盒子。此时便利度为 $2$，因为高度为 $3$ 和 $2$ 的重要盒子的底边分别落在区间 $[3,6]$ 内。 在第二个样例中，你必须把矮盒子放在高盒子下面。 由 ChatGPT 4.1 翻译