SHARE
TWEET

Untitled

a guest Jan 25th, 2020 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
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
Top