fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <numeric>
  4. using namespace std;
  5.  
  6. long my_gcd(long a, long b) {
  7.     while (b) {
  8.         a %= b;
  9.         swap(a, b);
  10.     }
  11.     return a;
  12. }
  13.  
  14. long my_lcm(long a, long b, long g) {
  15.     if (g == 0) return 0;
  16.     return (a / g) * b;
  17. }
  18.  
  19. bool can_finish(long t, long c1, long d1, long c2, long d2, long l) {
  20.     long s1_only = (t / c2) - (t / l);
  21.     long s2_only = (t / c1) - (t / l);
  22.     long s_shared = t - (t / c1) - (t / c2) + (t / l);
  23.     if (d1 > s1_only) d1 -= s1_only; else d1 = 0;
  24.     if (d2 > s2_only) d2 -= s2_only; else d2 = 0;
  25.     return (d1 + d2) <= s_shared;
  26. }
  27.  
  28. long minDeliveryTime(int charge1, int delivery1, int charge2, int delivery2) {
  29.     long c1 = charge1, d1 = delivery1, c2 = charge2, d2 = delivery2;
  30.     long g = my_gcd(c1, c2);
  31.     long l = my_lcm(c1, c2, g);
  32.     long low = 1, high = 4000000007LL, ans = high;
  33.     while (low <= high) {
  34.         long mid = low + (high - low) / 2;
  35.         if (can_finish(mid, c1, d1, c2, d2, l)) {
  36.             ans = mid;
  37.             high = mid - 1;
  38.         } else {
  39.             low = mid + 1;
  40.         }
  41.     }
  42.     return ans;
  43. }
  44.  
  45. int main() {
  46.     int a, b, c, d;
  47.     cin >> a >> b >> c >> d;
  48.     cout << minDeliveryTime(a, b, c, d) << endl;
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3 2 4 1
stdout
copy 
3
https://ideone.com/PA8aUB
language:
C++ (gcc 8.3)
created:
2 days 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!