Advertisement
Guest User

Untitled

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