close
  1. Problems
  2. classical
  3. Subset Sums
  1. Status
  2. Ranking

SUBSUMS - Subset Sums

#binary-search #bitmasks

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
Submit solution!
hide comments
Image theansh: 2024-02-08 17:52:22

am getting wrong answer

Last edit: 2024-02-08 17:53:25
Image charchitmangal: 2023-02-24 11: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 02:01:38
Image sachin_08: 2023-02-08 18:30:31

Meet

Image pranjal_noob: 2022-11-08 21:09:07

use upper_bound
Image 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.
Image 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
Image c_shekhar: 2022-02-04 14:29:44

1
-2
3

Image mohit_d12: 2022-02-02 06: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).
Image 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
Image 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

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.