Advertisement
Guest User

Untitled

a guest
Jan 26th, 2020
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<set>
  5. #include<cmath>
  6. #include<math.h>
  7. #include<iomanip>
  8. using namespace std;
  9. #define int ld
  10. typedef long double ld;
  11. signed main()
  12. {
  13. cout << fixed << setprecision(10);
  14. ios_base::sync_with_stdio(0);
  15. cin.tie(0); cout.tie(0);
  16. int n, m, t;
  17. cin >> n >> m >> t;
  18. ld r = 0;
  19. vector<pair<ld, ld > > a(n);
  20. for (int i = 0; i < n; ++i) {
  21. ld s, p;
  22. cin >> s >> p;
  23. r += s;
  24. a[i] = make_pair(p, s);
  25. }
  26. sort(a.begin() , a.end());
  27. int cnt = 0;
  28. ld l = 0;
  29. vector<ld> c(n);
  30. while (cnt < 1000) {
  31. ld mid = (r + l) / 2;
  32. int j = 0;
  33. ld mid1 = mid;
  34. while (mid1 > 0) {
  35. mid1 -= a[j].second;
  36. c[j] = a[j].second;
  37. j++;
  38. }
  39. if (mid1 < 0) {
  40. c[j - 1] += mid1;
  41. j--;
  42. }
  43. for (int e = 0; e < j + 1; ++e) {
  44. c[e] *= (a[e].first + 1000000.0) / 1000000.0;
  45. }
  46. int k = 0;
  47. bool check = true;
  48. while (k < m && check) {
  49. ld t1 = t;
  50. while (t1 > 0 && j > -1) {
  51. t1 -= c[j];
  52. c[j] = 0;
  53. j--;
  54. }
  55. if (t1 < 0) {
  56. c[j + 1] -= t1;
  57. j++;
  58. }
  59. for (int e = 0; e < j + 1; ++e) {
  60. c[e] *= (a[e].first+1000000.0) / 1000000.0;
  61. }
  62. if (c[0] <= 0) {
  63. check = false;
  64. }
  65. k++;
  66. }
  67. if (c[0] <= 0) {
  68. l = mid;
  69. }
  70. else {
  71. r = mid;
  72. }
  73. cnt++;
  74. c.clear();
  75. c.resize(n);
  76. }
  77. cout << l;
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement