SUBSUMS - Subset Sums

Given a sequence of N (1 ≤ N ≤ 34) numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 20,000,000), determine how many subsets of S (including the empty one) have a sum between A and B (-500,000,000 ≤ A ≤ B ≤ 500,000,000), inclusive.

Input

The first line of standard input contains the three integers N, A, and B. The following N lines contain S1 through SN, in order.

Output

Print a single integer to standard output representing the number of subsets satisfying the above property. Note that the answer may overflow a 32-bit integer.

Example

Input:
3 -1 2
1
-2
3

Output:
5

The following 5 subsets have a sum between -1 and 2:

  • 0 = 0 (the empty subset)
  • 1 = 1
  • 1 + (-2) = -1
  • -2 + 3 = 1
  • 1 + (-2) + 3 = 2

Added by:Neal Wu
Date:2009-01-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO

hide comments
2019-04-02 05:52:05
Nice problem! AC in one go! Binary Search Tree required!
2019-01-24 08:18:45
hay
2018-01-22 00:50:58
Be careful with the overflow ;)
2017-09-17 08:31:54
learnt alot !! after 2WA and 4TLE finally AC!!
2017-09-14 08:58:41
Meet in the middle..
2017-07-18 12:48:32
Can anyone please tell me what are some corner test cases ?.Because I am getting wrong Answer.
2017-06-29 18:13:58
Meet in the middle :)
2017-06-22 11:02:01
Empty subset should either be considered or not considered in the final value.
Its value being 0 seems a little wrong.
Cost me 2 WA :)

Last edit: 2017-06-22 11:23:48
2017-06-21 15:33:03
Nice problem!! Take care whether the empty subset sum lies in the range [a,b] or not.
Also STL made it a lot easier!!
2017-06-19 17:36:09
ac finally :)
it took my whole day to learn bitmask and meet in the middle approach :)
worth giving the time . must do
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.