Advertisement
Guest User

Untitled

a guest
Jan 27th, 2020
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<set>
  5. #include<cmath>
  6. #include<math.h>
  7. #include<iomanip>
  8. using namespace std;
  9. #define int long long
  10. typedef long double ld;
  11. ld poww(ld a, int b) {
  12.     if (b == 0) {
  13.         return 1;
  14.     }
  15.     if (b % 2 == 0) {
  16.         ld p = poww(a, b / 2);
  17.         return p*p;
  18.     }
  19.     else {
  20.         return a * poww(a, b - 1);
  21.     }
  22. }
  23. signed main()
  24. {
  25.     cout << fixed << setprecision(10);
  26.     ios_base::sync_with_stdio(0);
  27.     cin.tie(0); cout.tie(0);
  28.     int n, m, t;
  29.     cin >> n >> m >> t;
  30.     ld r = 0;
  31.     vector<pair<ld, ld > > a(n);
  32.     for (int i = 0; i < n; ++i) {
  33.         ld s, p;
  34.         cin >> s >> p;
  35.         r += s;
  36.         a[i] = make_pair(p, s);
  37.     }
  38.     sort(a.begin() , a.end());
  39.     int cnt = 0;
  40.     ld l = 0;
  41.     vector<ld> c(n);
  42.     while (cnt < 1000) {
  43.         ld mid = (r + l) / 2;
  44.         int j = 0;
  45.         ld mid1 = mid;
  46.         while (mid1 > 0) {
  47.             mid1 -= a[j].second;
  48.             c[j] = a[j].second*(1000000.0 + a[j].first)/1000000.0;
  49.             j++;
  50.         }
  51.         if (mid1 < 0) {
  52.             c[j - 1] = (a[j-1].second+mid1)*(1000000.0+a[j-1].first)/1000000.0;
  53.             j--;
  54.         }
  55.         int k = 0;
  56.         bool check = true;
  57.         ld t1 = t;
  58.         while (k < m) {
  59.             if (t1 < c[j]) {
  60.                 c[j] -= t1;
  61.                 c[j] *= (a[j].first+1000000.0)/1000000.0;
  62.                 k++;
  63.                 t1 = t;
  64.                 continue;
  65.             }
  66.             t1 -= c[j];
  67.             c[j] = 0;
  68.             j--;
  69.             if (c[0] <= 0) {
  70.                 break;
  71.             }
  72.             c[j] *= poww((a[j].first + 1000000.0) / 1000000.0, k);
  73.         }
  74.         if (c[0] <= 0) {
  75.             l = mid;
  76.         }
  77.         else {
  78.             r = mid;
  79.         }
  80.         cnt++;
  81.         c.clear();
  82.         c.resize(n);
  83.     }
  84.     cout << l;
  85.     return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement