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
2024-02-08 16:52:22
am getting wrong answer

Last edit: 2024-02-08 16:53:25
2023-02-24 10:11:24
I am getting wrong answer with below code, can someone please help me out->>>>>>
<snip>
[Simes]: Read the footer - Don't post source code here, use the forum.


Last edit: 2023-02-25 01:01:38
2023-02-08 17:30:31
Meet
2022-11-08 20:09:07
use upper_bound
2022-09-02 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.
2022-07-27 13:19:19
I have a doubt.
If I am sorting the whole array from the start before division, then I am getting WA. If I am just sorting the right part, then I am getting accepted. I know that there is the need to sort only right since we are just binary searching upon that but even if I did sorted the whole array at the beginning then what is the issue?

Last edit: 2022-07-27 13:23:21
2022-02-04 13:29:44
1
-2
3
2022-02-02 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).
2021-09-02 10:54:16
Prerequisites: Meet in the meet algo. Don't waste much time come back after learning the aforementioned algo.

Last edit: 2021-09-03 09:03:47
2021-08-10 21:12:00
those who are finding difficulty in this, don't worry it is actually hard question
ps: instead of implementing binary search use upper and lower bound
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.