Guest User

Untitled

a guest
Sep 23rd, 2019
87
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