fork(1) download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7. typedef pair<int, int> P;
  8.  
  9. const int MN = 100100;
  10. int n, m, k;
  11. ll p, h[MN], a[MN];
  12. ll h2[MN];
  13. bool check(ll x) {
  14. fill_n(h2, n, x);
  15. priority_queue<P, vector<P>, greater<P>> q;
  16. for (int i = 0; i < n; i++) {
  17. if (h2[i] - m*a[i] >= 0) continue;
  18. q.push(P(h2[i]/a[i]-1, i));
  19. }
  20. int count = 0;
  21. for (; count < m*k; count++) {
  22. if (q.empty()) break;
  23. P hit = q.top(); q.pop();
  24. if (hit.first < count/k) return false;
  25. int i = hit.second;
  26. h2[i] += p;
  27. if (h2[i] - m*a[i] >= 0) continue;
  28. q.push(P(h2[i]/a[i]-1, i));
  29. }
  30. if (count > m*k) return false;
  31. for (int i = 0; i < n; i++) {
  32. if (h2[i] - m*a[i] >= h[i]) continue;
  33. count += (h[i] - (h2[i] - m*a[i]) + p-1) / p;
  34. if (count > m*k) return false;
  35. }
  36. return true;
  37. }
  38.  
  39. int main() {
  40. cin >> n >> m >> k >> p;
  41. for (int i = 0; i < n; i++) {
  42. cin >> h[i] >> a[i];
  43. }
  44.  
  45. ll l = 0, r = 1LL<<55;
  46. while (r-l > 1) {
  47. ll md = (l+r)/2;
  48. if (check(md)) {
  49. r = md;
  50. } else {
  51. l = md;
  52. }
  53. }
  54. cout << r << endl;
  55. return 0;
  56. }
Success #stdin #stdout 0s 5492KB
stdin
Standard input is empty
stdout
1