fork(2) download
copy 
  1. /*
  2. 	Nishant Gupta
  3. 	nishant_141077
  4. 	MNNIT Allahabad
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #define LL long long int
  9. using namespace std;
  10.  
  11.  
  12. int niceness[50], n;
  13. vector<int> first_half[20];
  14. vector<int> sec_half[20];
  15.  
  16. void generate_subsets_first(int st, int end) {
  17. 	LL i = 0, j, sum = 0;
  18. 	LL mask;
  19. 	LL size = end - st + 1;
  20. 	for(mask=0;mask<(1<<size);mask++) {
  21. 		sum = 0;i = 0;
  22. 		for(j=0;j<size;j++) {
  23. 			if(!((1<<j)&mask)) {
  24. 				sum += niceness[j];
  25. 				i++;
  26. 			}
  27. 		}
  28. 		first_half[i].push_back(sum);
  29. 	}
  30. }
  31.  
  32. void generate_subsets_second(int st, int end) {
  33. 	LL i = 0, j, sum = 0;
  34. 	LL mask;
  35. 	LL size = end - st + 1;
  36. 	for(mask=0;mask<(1<<size);mask++) {
  37. 		sum = 0;i = 0;
  38. 		for(j=0;j<size;j++) {
  39. 			if(!((1<<j)&mask)) {
  40. 				sum += niceness[st+j];
  41. 				i++;
  42. 			}
  43. 		}
  44. 		sec_half[i].push_back(sum);
  45. 	}
  46. }
  47.  
  48. int main() {
  49. 	int i, j, k, a, b, x;
  50. 	cin>>n>>k>>a>>b;
  51. 	for(i=0;i<n;i++) {
  52. 		cin>>x;
  53. 		niceness[i] = 1;
  54. 		for(j=2;j*j<=x;j++) {
  55. 			if(x%j == 0) {
  56. 				niceness[i] = niceness[i]*j;
  57. 			}
  58. 			while(x%j == 0) {
  59. 				x/=j;
  60. 			}
  61. 		}
  62. 		if(x > 1) {
  63. 			niceness[i] = niceness[i]*x;
  64. 		}
  65. 	}
  66.  
  67. 	int mid = (n-1)/2;
  68. 	int size = n - mid -1;
  69. 	generate_subsets_first(0, mid);
  70. 	generate_subsets_second(mid+1, n-1);
  71.  
  72. 	for(i=0;i<=size;i++) {
  73. 		sort(sec_half[i].begin(), sec_half[i].end());
  74. 	}
  75. 	int t;
  76. 	LL ans = 0;
  77. 	for(i=0;i<=mid+1;i++) {
  78. 		for(j=0;j<first_half[i].size();j++) {
  79. 			int sum = first_half[i][j];
  80. 			int upto = min(k-i, size);
  81. 			int copy = ans;
  82. 			for(t=0;t<=upto;t++) {  //length of subsets in second half
  83. 				int upper = upper_bound(sec_half[t].begin(), sec_half[t].end(), b-sum) - sec_half[t].begin();
  84. 				int lower = lower_bound(sec_half[t].begin(), sec_half[t].end(), a-sum) - sec_half[t].begin();
  85. 				ans = ans + (upper -lower); 
  86. 			}
  87. 		}
  88. 	}
  89. 	cout<<ans<<endl;
  90. 	return 0;
  91. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/2BtlKG
language:
C++14 (clang 8.0)
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!