fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<tuple>
  4. using namespace std;
  5.  
  6. #define MAX_N 1200000
  7.  
  8. long long x1_AB[MAX_N];
  9. long long x1_AC[MAX_N];
  10. long long x2_AB[MAX_N];
  11. long long x2_AC[MAX_N];
  12. long long x1_E[MAX_N];
  13. long long x2_E[MAX_N];
  14. tuple<long long, long long, long long>x2_ALL[MAX_N];
  15. long long n, d, f, a[30], mid1, mid2, A, B, C, E, P, M1, M2, P1, P2, sum;
  16. long long power[30], cnt, cnt2;
  17.  
  18. int main() {
  19. 	power[0] = 1; for (int i = 1; i < 30; i++) { power[i] = power[i - 1] * 4; }
  20. 	cin >> n >> d >> f;
  21. 	for (int i = 0; i < n; i++) {
  22. 		cin >> a[i];
  23. 	}
  24.  
  25. 	mid1 = n / 2;
  26. 	mid2 = n - mid1;
  27.  
  28. 	cnt = 0;
  29.  
  30. 	for (int i = 0; i < power[mid1]; i++) {
  31. 		A = 0; B = 0; C = 0; E = 0;
  32. 		for (int j = 0; j < mid1; j++) {
  33. 			P = (i / power[j]) % 4;
  34. 			if (P == 0) {
  35. 				A += a[j];
  36. 			}
  37. 			if (P == 1) {
  38. 				B += a[j];
  39. 			}
  40. 			if (P == 2) {
  41. 				C += a[j];
  42. 			}
  43. 			if (P == 3) {
  44. 				E += 1;
  45. 			}
  46. 		}
  47. 		if (E <= f) {
  48. 			x1_AB[cnt] = A - B;
  49. 			x1_AC[cnt] = A - C;
  50. 			x1_E[cnt] = E;
  51. 			cnt++;
  52. 		}
  53. 	}
  54.  
  55. 	cnt2 = 0;
  56.  
  57. 	for (int i = 0; i < power[mid2]; i++) {
  58. 		A = 0; B = 0; C = 0; E = 0;
  59. 		for (int j = 0; j < mid2; j++) {
  60. 			P = (i / power[j]) % 4;
  61. 			if (P == 0) {
  62. 				A += a[j + mid1];
  63. 			}
  64. 			if (P == 1) {
  65. 				B += a[j + mid1];
  66. 			}
  67. 			if (P == 2) {
  68. 				C += a[j + mid1];
  69. 			}
  70. 			if (P == 3) {
  71. 				E += 1;
  72. 			}
  73. 		}
  74. 		if (E <= f) {
  75. 			x2_AB[cnt2] = A - B;
  76. 			x2_AC[cnt2] = A - C;
  77. 			x2_E[cnt2] = E;
  78. 			cnt2++;
  79. 		}
  80. 	}
  81.  
  82. 	for (int i = 0; i < cnt2; i++) {
  83. 		x2_ALL[i] = make_tuple(x2_AB[i], x2_AC[i], x2_E[i]);
  84. 	}
  85.  
  86. 	sort(x2_ALL, x2_ALL + cnt2);
  87.  
  88. 	for (int i = 0; i < cnt2; i++) {
  89. 		x2_AB[i] = get<0>(x2_ALL[i]);
  90. 		x2_AC[i] = get<1>(x2_ALL[i]);
  91. 		x2_E[i] = get<2>(x2_ALL[i]);
  92. 	}
  93.  
  94. 	for (int i = 0; i < cnt; i++) {
  95. 		M1 = -x1_AB[i] - d;
  96. 		M2 = -x1_AB[i] + d;
  97. 		P1 = lower_bound(x2_AB, x2_AB + cnt2, M1) - x2_AB;
  98. 		P2 = upper_bound(x2_AB, x2_AB + cnt2, M2) - x2_AB;
  99. 		for (int j = P1; j < P2; j++) {
  100. 			if (abs(x1_AC[i] + x2_AC[j]) <= d && x1_E[i] + x2_E[j] <= f) {
  101. 				sum++;
  102. 			}
  103. 		}
  104. 	}
  105.  
  106. 	cout << sum << endl;
  107.  
  108. 	return 0;
  109. }
Success #stdin #stdout 0s 87808KB
comments (?)
stdin
copy 
4 1 1
1
2
3
4
stdout
copy 
10
https://ideone.com/VGdQrk
language:
C++14 (gcc 8.3)
created:
8 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!