Advertisement
Guest User

Untitled

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