Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. //#pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. //#define int int64_t
  4. #define all(x) (x).begin(), (x).end()
  5. #define out(x) return void(cout << x << endl)
  6. #define OUT(x) ((cout << x), exit(0))
  7. using namespace std;
  8. typedef long double db;
  9. const int64_t INF = (int64_t)(2e18);
  10. const int inf = (int)(1e9 + 7);
  11. const db eps = (db)1e-9;
  12. //------------------------------------------//
  13.  
  14. inline bool eq(db a, db b) { return abs(a - b) < eps; }
  15. vector<pair<db, db>> ar;
  16. vector<db> k;
  17.  
  18. bool check(db mid, int m, db t) {
  19. fill(all(k), 0);
  20. for (int i = 0; i < ar.size() && !eq(mid, 0); ++i) {
  21. k[i] = (min(mid, ar[i].first));
  22. mid -= k[i];
  23. }
  24.  
  25. int i = (int)k.size() - 1;
  26. int day = 1;
  27. while (true) {
  28. db cur = t;
  29. while (!eq(cur, 0)) {
  30. db mult = pow(1 + ar[i].second, day);
  31. db member = t / mult;
  32. db s = t * (1 + ar[i].second) / ar[i].second;
  33. if (s < k[i]) return false;
  34. if (mult > 1e40) return false;
  35. db now = min(k[i], cur / mult);
  36. k[i] -= now;
  37. cur -= now * mult;
  38. if (eq(k[i], 0)) --i;
  39. if (i < 0) return true;
  40. }
  41.  
  42.  
  43. ++day;
  44. if (day > m) return false;
  45. }
  46.  
  47. }
  48.  
  49.  
  50. int32_t main()
  51. {
  52. ios_base::sync_with_stdio(false);
  53. cout << fixed << setprecision(40);
  54. cin.tie(nullptr);
  55.  
  56. #ifdef _MY
  57. freopen("input.txt", "r", stdin);
  58. freopen("output.txt", "w", stdout);
  59. #endif
  60.  
  61. int n, m;
  62. int tmpt;
  63. db t;
  64. cin >> n >> m >> tmpt;
  65. t = tmpt;
  66.  
  67. k.resize(n);
  68. ar.resize(n);
  69. for (auto& it : ar) {
  70. int a;
  71. cin >> a; it.first = a;
  72. cin >> a; it.second = a / 1000000.0;
  73. }
  74.  
  75. sort(all(ar), [](pair<db, db> a, pair<db, db> b) {return a.second < b.second; });
  76.  
  77. db l = 0;
  78. db r = 0;
  79. for (auto& it : ar) r += it.first;
  80. r = min(r, m * t);
  81.  
  82. for (int i = 0; i < 100; ++i) {
  83. if (eq(l, r)) break;
  84. db mid = (l + r) / 2;
  85. if (check(mid, m, t)) l = mid;
  86. else r = mid;
  87. }
  88.  
  89. cout << r;
  90.  
  91. return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement