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
karan:
20150619 16:04:53
nice problem :) 

Aman:
20150529 19:27:43
Last edit: 20150529 19:29:11 

i_am_looser:
20150524 16:58:18
Finally AC.............. ; ) 

prateek goyal:
20150524 15:17:35
\m 100th on spoj feeling relaxed :)


Rocker3011:
20150213 03:30:19
finally did this problem, it took me 2 years of training to be able to solve it with ease, :) 

ashish kumar:
20141229 15:45:54
wrong ans on 15th testcase 

Archit Jain:
20140814 13:27:08
nice concept 

selfcompiler:
20140812 05:37:30
:D it gives TLE ,use Fast Fourier Transformation :) 

innovolt:
20140326 18:44:17
start from brute force and then small optimization,not too tough as it seems... 

paras meena:
20140215 20:19:28
I think weak Test cases =P 
Added by:  Neal Wu 
Date:  20090119 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 