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

hide comments
shad_152: 2021-06-23 14:17:54

very basic and straight forward problem just meet in middle and binary search.

dazzler18: 2021-06-02 10:53:13

Use long long int and fast i/p & o/p
ios_base::sync_with_stdio(false);
cin.tie(NULL);

f_alam2000: 2021-05-20 13:26:00

Use long long int.

prabhav401: 2021-05-04 12:34:13

AC in one go 0_0
Really amazing question , teaches you so much !
try on your own till the end , trust me

mahak_rawat: 2021-04-05 17:33:21

Getting wrong answer in 14th test case. Can anyone help?

aviral_tiwari: 2021-02-18 12:05:10

Take Care of duplicates in array....Use lower and upper bound accordingly..

reaped_juggler: 2021-02-14 09:48:53

Be Careful on the condition while applying STL :) cost me 3 WA

nil_s: 2021-02-13 13:57:39

Getting WA on 14th testcase . Anybody can help??

hackerbhaiya: 2021-01-02 16:07:01

starter of meet in the middle algorithm :)

daddys_home: 2020-12-28 16:39:53

learn meet in the middle coz of this problem.
https://www.geeksforgeeks.org/meet-in-the-middle/


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