SHARE
TWEET

Untitled

a guest Sep 23rd, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<cmath>
  3. #include<algorithm>
  4. #include<vector>
  5.  
  6. using namespace std;
  7. using ll = long long;
  8. using ull = unsigned long long;
  9. ull mid = 0;
  10.  
  11. struct jewel{
  12.     ull id;
  13.     ull v;
  14.     ull w;
  15. };
  16.  
  17. bool comp(jewel a1, jewel a2){
  18.     return ((a1.v - mid * a1.w) < (a2.v - mid * a2.w));
  19. }
  20.  
  21.  
  22. int main() {
  23.     ios_base::sync_with_stdio(false);
  24.     cin.tie(nullptr);
  25.  
  26.     ull n, k;
  27.     cin >> n >> k;
  28.  
  29.     vector<jewel> vec(n);
  30.  
  31.     cin >> vec[0].v >> vec[0].w;
  32.     vec[0].id = 0;
  33.  
  34.     ull max = vec[0].v;
  35.     ull min = vec[0].w;
  36.  
  37.     for(ull i = 1; i < n; ++i){
  38.         cin >> vec[i].v >> vec[i].w;
  39.         vec[i].id = i;
  40.         if (vec[i].v > max) max = vec[i].v;
  41.         if (vec[i].w < min) min = vec[i].w;
  42.     }
  43.  
  44.     //диапазоны бин поиска, идем по ответу
  45.  
  46.     ull l = 0; //включая
  47.     ull r = max / min + 1; //не включая
  48.     ull sum = 0;
  49.  
  50.     while(r - l > 1){
  51.         mid = (l + r) / 2;
  52.         sort(vec.begin(), vec.end(), comp);
  53.         for(ull i = n - k; i < n; ++i){
  54.             sum += vec[i].v - mid * vec[i].w;
  55.         }
  56.         if (sum < 0) l = mid + 1;
  57.         else r = mid;
  58.         sum = 0;
  59.     }
  60.  
  61.     cout << mid;
  62.  
  63.    
  64.     return 0;
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top