fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. map<ll,ll> m1,m2;
  6.  
  7. int main()
  8. {
  9. 	ll n,s,i,v;
  10. 	cin>>n>>s;
  11.  
  12. 	ll d[n],j;
  13. 	for(i=0;i<n;i++)cin>>d[i];
  14.  
  15. 	ll s1 = n/2;
  16. 	ll s2 = n-s1;
  17.  
  18. 	ll a[s1],b[s2];
  19.  
  20. 	for(i=0;i<n;i++)
  21. 	{
  22. 		if(i<s1)
  23. 		{
  24. 			a[i] = d[i];
  25. 		}
  26. 		else
  27. 		{
  28. 			b[i-s1] = d[i];
  29. 		}
  30. 	}
  31.  
  32. 	ll ans = 0,val;
  33.  
  34. 	v = pow(2,s1);
  35.  
  36. 	for(i=0;i<v;i++)
  37. 	{
  38. 		val = 0;
  39. 		for(j=0;j<s1;j++)
  40. 		{
  41. 			if(i & (1<<j))
  42. 			{
  43. 				val+=a[j];
  44. 			}
  45. 		}
  46.  
  47. 		if(m1.find(val)==m1.end())
  48. 		{
  49. 			m1[val] = 1;
  50. 		}
  51. 		else
  52. 		{
  53. 			m1[val]++;
  54. 		}
  55.  
  56. 	}
  57.  
  58. 	v = pow(2,s2);
  59.  
  60. 	for(i=0;i<v;i++)
  61. 	{
  62. 		val = 0;
  63. 		for(j=0;j<s2;j++)
  64. 		{
  65. 			if(i & (1<<j))
  66. 			{
  67. 				val+=b[j];
  68. 			}
  69. 		}
  70.  
  71. 		if(m2.find(val)==m2.end())
  72. 		{
  73. 			m2[val] = 1;
  74. 		}
  75. 		else
  76. 		{
  77. 			m2[val]++;
  78. 		}
  79.  
  80. 	}
  81.  
  82. 	map<ll,ll>::iterator it,it1;
  83.  
  84.  
  85. 	for(it=m1.begin();it!=m1.end();++it)
  86. 	{
  87. 		v = s - (it->first);
  88.  
  89. 		if(v>=0)
  90. 		{
  91. 			it1 = m2.find(v);
  92. 			if(it1!=m2.end())ans+=((it->second) * (it1->second));
  93. 		}
  94.  
  95. 	}
  96. 	cout<<ans;
  97. 	return 0;
  98. }
Success #stdin #stdout 0s 3236KB
comments (?)
stdin
copy 
2 3
3 3
stdout
copy 
2
https://ideone.com/Ooi7lm
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!