Advertisement
Guest User

Untitled

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