猫粮规划 - Problem

Problem D: 猫粮规划

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 128 MiB

Submit ProblemList Solved: 4 Submit Num: 4 Statistics ShowOff!

Description

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

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

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

Input

第一行，三个正整数

n, l, r

。

第二行， $n$ 个正整数，表示每一份食物含有的能量 $w [i]$ 。

Output

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

Sample Input Copy

4 70 85
10 10 20 50

Sample Output Copy

HINT

样例解释

所有方案如下：

选择食物 $1, 2, 4$ ，能量 $10 + 10 + 50 = 70$ ；
选择食物 $1, 3, 4$ ，能量 $10 + 20 + 50 = 80$ ；
选择食物 $2, 3, 4$ ，能量 $10 + 20 + 50 = 80$ ；
选择食物 $3, 4$ ，能量 $50 + 20 = 70$ 。

共 $4$ 种方案。

数据规模与约定

对于 $50%$ 的数据，满足 $n \leq 20$ 。

对于 $100%$ 的数据，满足 $n \leq 40, 20 \leq w [i] \leq 100, l \leq r \leq 300$ 。

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

Submit