#B3624. 猫粮规划

猫粮规划

题目描述

到中午了,机器猫要吃猫粮了。

机器猫掏出 nn 份食物,第 ii 份食物含有的能量为 w[i]w[i]。机器猫可以吃掉其中一些食物,获得这些食物的能量之和。

机器猫又不想变得太胖又不想变得太瘦,所以指定了一个目标区间 [l,r][l, r]。显然,可能有很多种选择食物的方式可以达成这个目标,因此机器猫想知道方案总数。

输入格式

第一行,三个正整数 n,l,rn, l, r

第二行,nn 个正整数,表示每一份食物含有的能量 w[i]w[i]

输出格式

仅一行,一个整数,表示方案数。

4 70 85
10 10 20 50

4

提示

样例解释

所有方案如下:

选择食物 1, 2, 4,能量 10+10+50 = 70
选择食物 1, 4, 5,能量 10+20+50 = 80
选择食物 2, 3, 4,能量 10+20+50 = 80
选择食物 3, 4,能量 50+20 = 70

共 4 种方案。

数据规模与约定

对于 50%50\% 的数据,满足 n20n\leq 20

对于 100%100\% 的数据,满足 n40,20w[i]100,lr300n\leq 40, 20\leq w[i] \leq 100, l\leq r \leq 300

提示:w[i]w[i] 在范围内均匀随机生成。