Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.96 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 now = min(k[i], cur / mult);
  32. k[i] -= now;
  33. cur -= now * mult;
  34. if (eq(k[i], 0)) --i;
  35. if (i < 0)
  36. return true;
  37. }
  38.  
  39.  
  40. ++day;
  41. if (day > min(m, 100))
  42. return false;
  43. }
  44.  
  45. }
  46.  
  47.  
  48. int32_t main()
  49. {
  50. ios_base::sync_with_stdio(false);
  51. cout << fixed << setprecision(40);
  52. cin.tie(nullptr);
  53.  
  54. #ifdef _MY
  55. freopen("input.txt", "r", stdin);
  56. freopen("output.txt", "w", stdout);
  57. #endif
  58.  
  59. int n, m;
  60. int tmpt;
  61. db t;
  62. cin >> n >> m >> tmpt;
  63. t = tmpt;
  64.  
  65. k.resize(n);
  66. ar.resize(n);
  67. for (auto& it : ar) {
  68. int a;
  69. cin >> a; it.first = a;
  70. cin >> a; it.second = a / 1000000.0;
  71. }
  72.  
  73. sort(all(ar), [](pair<db, db> a, pair<db, db> b) {return a.second < b.second; });
  74.  
  75. db l = 0;
  76. db r = 0;
  77. for (auto& it : ar) r += it.first;
  78.  
  79. for (int i = 0; i < 100; ++i) {
  80. if (eq(l, r)) break;
  81. db mid = (l + r) / 2;
  82. if (check(mid, m, t)) l = mid;
  83. else r = mid;
  84. }
  85.  
  86. cout << r;
  87.  
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement