fork(2) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/AGflsb
language:
C++14 (gcc 8.3)
created:
9 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!