SHARE
TWEET

B

a guest Jan 26th, 2020 935 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <stack>
  7. #include <map>
  8. #include <set>
  9. #include <iomanip>
  10.  
  11. using namespace std;
  12.  
  13. void QuickStart() {
  14.     ios_base::sync_with_stdio(0); cin.tie(0);
  15. }
  16.  
  17. typedef long long ll;
  18. typedef double db;
  19.  
  20. using namespace std;
  21.  
  22. int rand_() {
  23.     return (rand() << 15) + rand();
  24. }
  25.  
  26. const int inf = 1e9;
  27. const db eps = 1e-7;
  28.  
  29. vector<pair<db, db> >bank;
  30.  
  31. int n, m;
  32. db t;
  33.  
  34. bool cmp(pair<db, db>& a, pair<db, db>& b) {
  35.     return a.first < b.first;
  36. }
  37.  
  38. bool f(db x) {
  39.     int end = -1;
  40.     vector<db>debt(n);
  41.     for (int i = 0; i < n; i++) {
  42.         if (x >= bank[i].first) {
  43.             debt[i] = bank[i].first;
  44.             x -= debt[i];
  45.         }
  46.         else {
  47.             debt[i] = x;
  48.             break;
  49.         }
  50.     }
  51.     for (int i = n - 1; i >= 0; i--) {
  52.         if (debt[i]) {
  53.             end = i;
  54.             break;
  55.         }
  56.     }
  57.     db tt = t;
  58.     for (int i = 0; i < m; i++) {
  59.         while (end >= 0 || t) {
  60.             debt[end] = pow(debt[end], bank[i].second + 1);
  61.             if (t >= debt[end]) {
  62.                 debt[end] = 0;
  63.                 t -= debt[end];
  64.                 end--;
  65.             }
  66.             else {
  67.                 debt[end] -= t;
  68.                 t = 0;
  69.             }
  70.         }
  71.         t = tt;
  72.     }
  73.     for (int i = 0; i < n; i++) {
  74.         if (debt[i] != 0.0) {
  75.             return 0;
  76.         }
  77.     }
  78.     return 1;
  79. }
  80.  
  81. db bs(db l, db r) {
  82.     while (r - l > eps) {
  83.         db m = (l + r) / 2;
  84.         if (f(m)) {
  85.             l = m;
  86.         }
  87.         else {
  88.             r = m;
  89.         }
  90.     }
  91.     return l;
  92. }
  93.  
  94. void solve()  {
  95.     cin >> n >> m >> t;
  96.     bank.resize(n);
  97.     db sum = 0;
  98.     for (int i = 0; i < n; i++) {
  99.         cin >> bank[i].first >> bank[i].second;
  100.         sum += bank[i].first;
  101.         bank[i].second /= 1e6;
  102.     }
  103.     sort(bank.begin(), bank.end(), cmp);
  104.     cout << fixed << setprecision(1e7) << bs(0, sum + 1);
  105. }
  106.  
  107. int main() {
  108.     QuickStart();
  109.     solve();
  110. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top