fork download
copy 
  1.  
  2. //Ayush Kushwaha MNNIT
  3. //meet in the middle logic
  4.  
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. #define ll int
  8. ll x[1000000],y[1000000];
  9. ll a[1000000];
  10.  
  11.  
  12. void subarray(ll a[],ll w[],ll n,ll c)
  13. {
  14. 	for(int i=0;i<(1<<n);i++)
  15. 	{
  16. 		ll s=1;
  17. 		for(int j=0;j<n;j++)
  18. 		if(i & (1<<j))
  19. 			s*=a[j+c];
  20.  
  21. 	w[i]=s;		
  22. 	}
  23. }
  24.  
  25. ll subsum(ll a[],ll n,ll f)
  26. {
  27. 	subarray(a,x,n,0);
  28. 	subarray(a,y,n-n/2,n/2);
  29. 	int sx=(1<<n/2);
  30. 	int sy=(1<<(n-n/2));
  31. 	sort(y,y+sy);
  32. 	int h=0,k=-100000;
  33. 	int d=0;
  34. 	for(int i=0;i<sx;i++)
  35. 	{
  36. 		if(x[i]<=f)
  37. 		   h+=lower_bound(y,y+sy,f/x[i])-y;
  38. 	}
  39. 	return h-1;
  40. }
  41.  
  42. int main()
  43. {
  44. 	ll n,f;
  45. 	cin>>n>>f;
  46. 	for(int i=0;i<n;i++)
  47. 	{
  48. 		cin>>a[i];
  49. 	}
  50. 	cout<<subsum(a,n,f);
  51. 	// cout<<p%f<<"\n";	
  52. }
Success #stdin #stdout 0s 4464KB
comments (?)
stdin
copy 
3 4
1 2 3
stdout
copy 
5
https://ideone.com/Pg6BJO
language:
C++14 (gcc 8.3)
created:
5 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!