Advertisement
GerONSo

Untitled

Jan 27th, 2020
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.00 KB | None | 0 0
  1. /*
  2.  
  3. ∧_∧
  4. ( ・ω・。)つ━☆・*。
  5. ⊂  ノ    ・゜
  6. しーJ   Accepted
  7.  
  8. */
  9.  
  10.  
  11.  
  12. // #pragma GCC optimize("O3")
  13. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  14.  
  15. #include <bits/stdc++.h>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. #define ll long long
  20. #define all(x) begin(x), end(x)
  21. #define x first
  22. #define y second
  23. #define int long long
  24.  
  25. using namespace std;
  26. using namespace __gnu_pbds;
  27.  
  28. typedef long double ld;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(14);
  39. #ifdef _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 1e5 + 10;
  46. const int MAXM = 600;
  47. const int INF = 1e18 + 7;
  48. const int BASE = 47;
  49. const int MOD = 998244353;
  50. const int MAXLOG = 61;
  51. const ld EPS = 1e-8;
  52.  
  53. ld binpow(ld a, int pw) {
  54. if(pw == 0) return 1;
  55. if(pw % 2) {
  56. return binpow(a, pw - 1) * a;
  57. }
  58. else {
  59. a *= a;
  60. return binpow(a, pw / 2);
  61. }
  62. }
  63.  
  64. signed main() {
  65. seriy();
  66. int n;
  67. ld m, t;
  68. cin >> n >> m >> t;
  69. vector<pair<ld, ld>> a(n);
  70. for(int i = 0; i < n; i++) {
  71. cin >> a[i].x >> a[i].y;
  72. a[i].y = (a[i].y / 1e6) + 1;
  73. }
  74. sort(all(a), [&](pair<ld, ld> a, pair<ld, ld> b) {
  75. return a.y < b.y;
  76. });
  77. // for(auto i : a) {
  78. // cerr << i.x << " " << i.y << '\n';
  79. // }
  80. vector<ld> pw(n);
  81. for(int i = 0; i < n; i++) {
  82. pw[i] = binpow(a[i].y, m);
  83. }
  84. int cnt = 100;
  85. ld l = 0, r = INF;
  86. while(cnt--) {
  87. ld mid = (l + r) / 2.;
  88. ld need = mid;
  89. ld sum = 0;
  90. vector<ld> cnt(n), now(n), start(n);
  91. for(int i = 0; i < n; i++) {
  92. ld can = min(need, a[i].x);
  93. cnt[i] = can;
  94. start[i] = can;
  95. need -= can;
  96. }
  97. int cur = n - 1;
  98. for(int i = 0; i < m; i++) {
  99. ld tt = t;
  100. while(tt > 0) {
  101. // cerr << tt << '\n';
  102. if(abs(cnt[cur] - now[cur]) < EPS) {
  103. cur--;
  104. }
  105. if(cur < 0) break;
  106. // cerr << a[cur].y << '\n';
  107. cnt[cur] = start[cur] * binpow(a[cur].y, i);
  108. // cerr << cur << '\n';
  109. // cerr << abs(cnt[cur] - now[cur]) << " " << tt << '\n';
  110. ld out = min(abs(cnt[cur] - now[cur]), tt);
  111.  
  112. now[cur] += out;
  113. tt -= out;
  114. }
  115. if(cur < 0) break;
  116. }
  117. if(abs(cnt[0] - now[0]) < EPS) {
  118. l = mid;
  119. }
  120. else {
  121. r = mid;
  122. }
  123. }
  124. cout << r;
  125. return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement