Advertisement
Guest User

Untitled

a guest
May 26th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.74 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<int> 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<int>& 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. if (mid >= ceil(((double)(z - goo[mid])) / k)){
  72. r = mid;
  73. } else{
  74. l = mid;
  75. }
  76. }
  77. return r;
  78. }
  79.  
  80. int main(){
  81. // freopen("coins.in", "r", stdin);
  82. // freopen("coins.out", "w", stdout);
  83. // cout.precision(10);
  84. // cout << fixed;
  85. // ifstream fin("input.txt");
  86. cin.tie(0);
  87. ios_base::sync_with_stdio(false);
  88. int n, x, k;
  89. cin >> n >> x >> k;
  90. long long z = 0;
  91. int w = 0;
  92. heap goo;
  93. goo.a.push_back(0);
  94. for (int i = 0; i < n; ++i){
  95. int f;
  96. cin >> f;
  97. z += f;
  98. if (x != 0){
  99. w += f / x;
  100. f %= x;
  101. }
  102. if (f != 0){
  103. goo.a.push_back(f);
  104. goo.up(goo.a.size() - 1);
  105. }
  106. }
  107. vector<int> koo;
  108. for (int i = 0; i < w; ++i){
  109. if (i == 0){
  110. koo.push_back(x);
  111. continue;
  112. }
  113. koo.push_back(koo[i - 1] + x);
  114. }
  115. while (goo.a.size() > 1){
  116. if (koo.size() == 0){
  117. koo.push_back(goo.a[1]);
  118. } else{
  119. koo.push_back(koo[koo.size() - 1] + goo.a[1]);
  120. }
  121. goo.del();
  122. }
  123. cout << Binss(koo, z, k);
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement