fork(1) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<climits>
  4. #include<cstring>
  5. #include<fstream>
  6. #include<vector>
  7. #define all(a) a.begin(), a.end()
  8. #define fr(i, zz, zzz) for (int i = zz; i <= zzz; i++)
  9. #define ll long long
  10. #define pii pair<int, int>
  11. #define frr(i, zz, zzz) for (int i = zz; i >= zzz; i--)
  12. #define full(asdf) memset(asdf, 0, sizeof(asdf))
  13. #define st first
  14. #define nd second
  15. #define IOS ios_base::sync_with_stdio(0);   cin.tie(0); cout.tie(0);
  16. using namespace std;
  17. const int N = 1E6+1;
  18. int a[5005], n, k;
  19. ll c[N], mn = LLONG_MAX;
  20. vector<ll> res, ress;
  21. void Try(int i, int en, int sum, vector<ll>& p) {
  22. 	if (sum + (en - i)*mn > k)
  23. 		return;	
  24. 	if (i > en) {
  25. 		p.push_back(sum);
  26. 		return;
  27. 	}
  28.  
  29. 	else  {
  30. 		Try(i+1, en, sum + a[i], p);
  31. 		Try(i+1, en, sum, p);
  32. 	}
  33. }
  34. int main () {
  35. 	IOS
  36. 	fstream f,g;
  37. 	f.open("FAIR.INP", ios::in);
  38. 	g.open("FAIR.OUT", ios::out);
  39. 	int cnt = 0;
  40. 	f >> n >> k;
  41. 	fr(i, 1, n) {
  42. 		f >> a[i]; 
  43. 		mn = min(mn, (ll)a[i]);
  44. 		}
  45. 	if (k == 0) {
  46. 		g << 1;
  47. 		return 0;
  48. 	}
  49. 	if (n <= 40) {
  50. 	Try(1, n/2, 0, res);
  51. 	Try(n/2+1, n, 0, ress);
  52. /*	
  53. 	for (int x : res)
  54. 		cout << x << " ";
  55. 	cout << "\n";
  56. 	for (int x : ress)
  57. 		cout << x << " ";
  58. 	cout << "\n";
  59. 	*/
  60. 	fr(i, 0, res.size() - 1) {
  61. 		if (res[i] != -1) {
  62. 			if (res[i] == k) {
  63. 				++cnt;
  64. 				res[i] = -1;
  65. 			}
  66. 			else {
  67. 				fr(j, 0, ress.size() - 1) {
  68. 					if (ress[j] != -1) {
  69. 						if (ress[j] == k) {
  70. 							++cnt;
  71. 							ress[j] = -1;
  72. 						}
  73. 						else {
  74. 							if (res[i] + ress[j] == k) {
  75. 								++cnt;
  76. 							}
  77. 						}
  78. 					}
  79. 				}
  80. 			}
  81. 		}
  82. 	}
  83. 	g << cnt % 123456789;
  84. 	return 0;
  85. 	}
  86. 	else {	
  87. 		ll s = 0;
  88. 		full(c);
  89. 		c[0] = 1;
  90. 		fr(i, 1, n) {
  91. 			if (s + a[i] < k) 
  92. 				s += a[i];
  93. 			else
  94. 				s = k;
  95. 			frr(j, s, a[i]) {
  96. 				if (c[j - a[i]] != 0) 
  97. 					c[j] = (c[j] + c[j - a[i]]) % 123456789;
  98. 			}
  99. 		}
  100. 		g << c[k];
  101. 	}
  102. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lN2YSP
language:
C++14 (gcc 8.3)
created:
1 year 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!