fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <cstring>
  21. #include <climits>
  22. #include <stdlib.h>
  23. #include <stdio.h>
  24. using namespace std;
  25. #define REP(i,n) for(int i=0; i<n; i++)
  26. #define FOR(i,st,end) for(int i=st;i<end;i++)
  27. #define db(x) cout << (#x) << " = " << x << endl;
  28. #define mp make_pair
  29. #define pb push_back
  30. typedef long long int ll;
  31. int main(){
  32. 	ll n,a,b;
  33. 	ll arr[40];
  34. 	ll subSetSize;
  35. 	vector<ll>sum1;
  36. 	vector<ll>sum2;
  37. 	scanf("%lld%lld%lld",&n,&a,&b);
  38. 	REP(i,n){
  39. 		scanf("%lld",&arr[i]);
  40. 	}
  41. 	ll powerSetSize=1<<n/2;
  42. 	subSetSize=n/2;
  43. 	//finding subset sum for first half
  44. 	for(ll i=0;i<powerSetSize;i++){
  45. 		ll sum=0;
  46. 		REP(j,subSetSize){
  47. 			if(i&(1<<j)){
  48. 				sum+=arr[j];
  49. 			}
  50. 		}
  51. 		sum1.pb(sum);
  52. 	}
  53. 	//this is to classify even and odd n cases
  54.     if((n&1)==1){
  55.  
  56. 		subSetSize=n/2+1;
  57. 		powerSetSize=1<<subSetSize;
  58. 	}
  59. 	else{
  60.  
  61. 		subSetSize=n/2;
  62. 		powerSetSize=1<<subSetSize;
  63. 	}
  64. 	//finding subset sum for 2nd half
  65. 	for(ll i=0;i<powerSetSize;i++){
  66. 		ll sum=0;
  67. 		REP(j,subSetSize){
  68. 			if(i&(1<<j)){
  69. 				sum+=arr[n/2+j];
  70. 			}
  71. 		}
  72. 		sum2.pb(sum);
  73. 	}
  74. 	sort(sum1.begin(),sum1.end());
  75. 	vector<ll>::iterator low,high;
  76. 	ll ans=0;
  77. 	//use STL functions to find lower bounds and upper bounds(which internally uses binary search)
  78. 	REP(i,sum2.size()){
  79. 		low=lower_bound(sum1.begin(),sum1.end(),a-sum2[i]);//CAN SOMEONE EXPLAIN WHATS BEING DONE HERE
  80. 		high=upper_bound(sum1.begin(),sum1.end(),b-sum2[i]);//CAN SOMEONE EXPLAIN WHATS BEING DONE HERE
  81. 		ans+=(high-low);
  82. 	}
  83. 	printf("%lld\n",ans);
  84.  
  85. }
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
3 -1 2
1
-2
3
stdout
copy 
5
https://ideone.com/SqeQno
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!