fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #define ll long long int
  4. using namespace std;
  5. const long long MOD = 1e9 + 7;
  6.  
  7. // void debug(vector<ll> &arr) {
  8. //     for (auto it: arr) {
  9. //         cout << it << " ";
  10. //     }
  11. //     cout << endl;
  12. //     cout << endl;
  13. // }
  14. // void debug(vector<ll> &arr, int n) {
  15. //     for (int i = 0; i < n; i++) {
  16. //         cout << arr[i] << " ";
  17. //     }
  18. //     cout << endl;
  19. //     cout << endl;
  20. // }
  21.  
  22.  
  23.  
  24. ll lcm(ll a, ll b) {
  25.     return (a * b) / __gcd(a, b);
  26. }
  27. // ll get_msb(ll n) {
  28. //     for (int i = 31; i >= 0; i--) {
  29. //         if ((1 << i) & n) {
  30. //             return i + 1;
  31. //         }
  32. //     }
  33. //     return 1;
  34. // }
  35. bool is_possible(vector<ll> &arr, int n, ll t, ll time) {
  36.     ll total_products = 0;
  37.     for (auto it: arr) {
  38.         total_products += time / it;
  39.     }
  40.     return total_products >= t;
  41. }
  42.  
  43. int main()
  44. {
  45.     #ifndef ONLINE_JUDGE
  46.     freopen("input.txt","r",stdin); 
  47.     freopen("output.txt","w",stdout);
  48.     #endif
  49.  
  50.     int t = 1;
  51.     // cin >> t;
  52.     while(t--) {  
  53.       int n;
  54.       cin >> n;
  55.       ll k;
  56.       cin >> k;
  57.       vector<long double> arr(n, 0), brr(n, 0);
  58.       ll sum = 0;
  59.       for (int i = 0; i < n; i++) {
  60.         cin >> arr[i];
  61.         cin >> brr[i];
  62.         sum += arr[i];
  63.       }
  64.  
  65.       ll lo = 0, hi = sum;
  66.       long double ans = 0;
  67.       long double precision = 1e-7;
  68.  
  69.       ll itr = 0;
  70.       while (hi - lo >= precision) {
  71.         itr++;
  72.         if (itr == 100) break;
  73.         long double ratio = (lo + hi) / 2.0;
  74.         vector<long double> arr2(n, 0);
  75.         for (int i = 0; i < n; i++) {
  76.           arr2[i] = arr[i] - ratio * brr[i];
  77.         }
  78.         sort(arr2.begin(), arr2.end());
  79.         ll sum2 = 0;
  80.         ll count = 0;
  81.         for (int i = n - 1; i >= 0; i--) {
  82.             if (count == k) break;
  83.             sum2 += arr2[i];
  84.             count++;
  85.         }
  86.         if (sum2 < 0) {
  87.             hi = ratio - precision;
  88.         }
  89.         else {
  90.             lo = ratio + precision;
  91.             ans = max(ans, ratio);
  92.         }
  93.       }
  94.  
  95.       cout << ans << endl;
  96.    }
  97. }
  98.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/qmil6y
language:
C++14 (gcc 8.3)
created:
7 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!