anon20016

K

Nov 17th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <algorithm>
  9.  
  10. #define li long long
  11.  
  12. using namespace std;
  13.  
  14. li gcd(li a, li b) {
  15. return b ? gcd(b, a % b) : a;
  16. }
  17.  
  18. bool cmp(pair<pair<li, li>, li> a, pair<pair<li, li>, li> b) {
  19. return a.first.first * b.first.second > a.first.second * b.first.first;
  20. }
  21.  
  22. int main() {
  23. freopen("input.txt", "r", stdin);
  24. freopen("output.txt", "w", stdout);
  25.  
  26. int n, w;
  27. cin >> n >> w;
  28. vector<pair<pair<li, li>, li> > a(n);
  29. for (int i = 0; i < n; i++) {
  30. li q, w;
  31. cin >> q >> w;
  32. a[i] = {{ q, w }, w};
  33. li g = gcd(q, w);
  34. a[i].first.first = a[i].first.first / g;
  35. a[i].first.second = a[i].first.second / g;
  36. }
  37. sort(a.begin(), a.end(), cmp);
  38. pair<li, li> ans = { 0, 1 };
  39. for (int i = 0; i < a.size() && w; i++) {
  40. li k = a[i].second;
  41. if (w < a[i].second) {
  42. k = w;
  43. }
  44. w -= k;
  45. pair<li, li> r = { a[i].first.first * k, a[i].first.second };
  46. ans = { ans.first * r.second + ans.second * r.first, ans.second * r.second };
  47. li g = gcd(ans.first, ans.second);
  48. ans.first /= g;
  49. ans.second /= g;
  50. }
  51. if (ans.first / ans.second != 0) {
  52. cout << ans.first / ans.second << ' ';
  53. }
  54. if (ans.first % ans.second != 0) {
  55. cout << ans.first % ans.second << '/' << ans.second;
  56. }
  57. }
Advertisement
Add Comment
Please, Sign In to add comment