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
pranjal_noob: 2022-11-08 20:09:07

use upper_bound

kartikkk: 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.

uchiha98: 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
c_shekhar: 2022-02-04 13:29:44

1
-2
3

mohit_d12: 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).

devil_nero: 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
iq69: 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

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.


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