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
pranjal_noob:
20221108 20:09:07
use upper_bound 

kartikkk:
20220902 01:00:52
all the heroes in comment who are posting did one attempt or writing very basic question like that are fools , dont listen to them and try on your own , but this question is really hard and the approach used to actually solve the question needs to you to already know about subsets and subsequences and how to calculate them and more so dont worry and look it up on utube. 

uchiha98:
20220727 13:19:19
I have a doubt.


c_shekhar:
20220204 13:29:44
1


mohit_d12:
20220202 05:50:51
Earlier got a WA on test case 15, just needed to use long long int for the output variable (which stores the number of subsets). 

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. 
Added by:  Neal Wu 
Date:  20090119 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 