SUBSUMS  Subset Sums
Given a sequence of N (1 ≤ N ≤ 34) numbers S_{1}, ..., S_{N} (20,000,000 ≤ S_{i} ≤ 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 S_{1} through S_{N}, 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 32bit 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
hide comments
devil_nero:
20210902 10:54:16
Prerequisites: Meet in the meet algo. Don't waste much time come back after learning the aforementioned algo. Last edit: 20210903 09:03:47 

iq69:
20210810 21:12:00
those who are finding difficulty in this, don't worry it is actually hard question


shad_152:
20210623 14:17:54
very basic and straight forward problem just meet in middle and binary search. 

dazzler18:
20210602 10:53:13
Use long long int and fast i/p & o/p


f_alam2000:
20210520 13:26:00
Use long long int. 

prabhav401:
20210504 12:34:13
AC in one go 0_0


mahak_rawat:
20210405 17:33:21
Getting wrong answer in 14th test case. Can anyone help? 

aviral_tiwari:
20210218 12:05:10
Take Care of duplicates in array....Use lower and upper bound accordingly.. 

reaped_juggler:
20210214 09:48:53
Be Careful on the condition while applying STL :) cost me 3 WA 

nil_s:
20210213 13:57:39
Getting WA on 14th testcase . Anybody can help?? 
Added by:  Neal Wu 
Date:  20090119 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 