Advertisement
Guest User

Untitled

a guest
May 26th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <set>
  7. #include <string>
  8. #include <algorithm>
  9. #include <stack>
  10. #include <map>
  11. #include <fstream>
  12. #pragma GCC optimize("no-stack-protector")
  13. #pragma comment(linker, "/STACK:99999999999999999")
  14.  
  15. using namespace std;
  16.  
  17. const long double eps = 1e-10;
  18. const long double inf = 999999999999999;
  19. const long double pi = 3.141592653589793238462643383279;
  20.  
  21. ostream& operator << (ostream& out, const vector<long long>& s){
  22. for (int i = 0; i < s.size(); ++i){
  23. out << s[i] << ' ';
  24. }
  25. return out;
  26. }
  27.  
  28. ostream& operator << (ostream& out, pair<int, int>& a){
  29. out << a.first << ' ' << a.second;
  30. return out;
  31. }
  32.  
  33. struct heap{
  34. vector<long long> a;
  35.  
  36. void del(){
  37. swap(a[a.size() - 1], a[1]);
  38. a.pop_back();
  39. down(1);
  40. }
  41.  
  42. void up(int i){
  43. while (i > 1 && a[i] > a[i / 2]){
  44. swap(a[i], a[i/2]);
  45. i /= 2;
  46. }
  47. }
  48.  
  49. void down(int i){
  50. while (i * 2 < a.size()){
  51. int right = i * 2 + 1;
  52. int left = i * 2;
  53. int j = left;
  54. if (right < a.size() && a[right] > a[left]){
  55. j = right;
  56. }
  57. if (a[i] >= a[j]){
  58. break;
  59. }
  60. swap(a[i], a[j]);
  61. i = j;
  62. }
  63. }
  64.  
  65. };
  66.  
  67. long long Binss(const vector<long long>& goo, long long z, int k){
  68. int l = 0, r = goo.size();
  69. while (r - l > 1){
  70. int mid = (r + l) / 2;
  71. // cout << mid << ' ' << ceil((double)(z - goo[mid - 1]) / k) << '\n';
  72. if (mid == ceil((double)(z - goo[mid - 1]) / k)){
  73. return mid;
  74. }
  75. if (mid >= ceil((double)(z - goo[mid - 1]) / k)){
  76. r = mid;
  77. } else{
  78. l = mid;
  79. }
  80. }
  81. return r;
  82. }
  83.  
  84. int main(){
  85. // freopen("coins.in", "r", stdin);
  86. // freopen("coins.out", "w", stdout);
  87. // cout.precision(10);
  88. // cout << fixed;
  89. // ifstream fin("input.txt");
  90. cin.tie(0);
  91. ios_base::sync_with_stdio(false);
  92. long long n, x, k;
  93. cin >> n >> x >> k;
  94. long long z = 0;
  95. long long w = 0;
  96. heap goo;
  97. goo.a.push_back(0);
  98. for (int i = 0; i < n; ++i){
  99. int f;
  100. cin >> f;
  101. z += f;
  102. if (x != 0){
  103. w += f / x;
  104. f %= x;
  105. }
  106. if (f != 0){
  107. goo.a.push_back(f);
  108. goo.up(goo.a.size() - 1);
  109. }
  110. }
  111. if (x == 0){
  112. cout << ceil((double)z / k);
  113. exit(0);
  114. }
  115. if (k == 0){
  116. cout << w + goo.a.size() - 1;
  117. exit(0);
  118. }
  119. vector<long long> koo;
  120. for (int i = 0; i < w; ++i){
  121. if (i == 0){
  122. koo.push_back(x);
  123. continue;
  124. }
  125. koo.push_back(koo[i - 1] + x);
  126. }
  127. while (goo.a.size() > 1){
  128. if (koo.size() == 0){
  129. koo.push_back(goo.a[1]);
  130. } else{
  131. koo.push_back(koo[koo.size() - 1] + goo.a[1]);
  132. }
  133. goo.del();
  134. }
  135. // cout << koo << '\n';
  136. cout << Binss(koo, z, k);
  137. }
  138. /*
  139. 2 11 11
  140. 9
  141. 5
  142. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement