SPOJ.com - Problem SUBSUMS

SUBSUMS - Subset Sums

#binary-search #bitmasks

Given a sequence of N (1 ≤ N ≤ 34) numbers S₁, ..., 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₁ 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 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

< Previous 1 2 3 4 5 6 7 Next >

	theansh: 2024-02-08 16:52:22 am getting wrong answer Last edit: 2024-02-08 16:53:25
	charchitmangal: 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
	sachin_08: 2023-02-08 17:30:31 Meet
	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

Submit solution!

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