Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("O3")
- #include <bits/stdc++.h>
- //#define int int64_t
- #define all(x) (x).begin(), (x).end()
- #define out(x) return void(cout << x << endl)
- #define OUT(x) ((cout << x), exit(0))
- using namespace std;
- typedef long double db;
- const int64_t INF = (int64_t)(2e18);
- const int inf = (int)(1e9 + 7);
- const db eps = (db)1e-9;
- //------------------------------------------//
- inline bool eq(db a, db b) { return abs(a - b) < eps; }
- vector<pair<db, db>> ar;
- vector<db> k;
- bool check(db mid, int m, db t) {
- fill(all(k), 0);
- for (int i = 0; i < ar.size() && !eq(mid, 0); ++i) {
- k[i] = (min(mid, ar[i].first));
- mid -= k[i];
- }
- int i = (int)k.size() - 1;
- int day = 1;
- while (true) {
- db cur = t;
- while (!eq(cur, 0)) {
- db mult = pow(1 + ar[i].second, day);
- db member = t / mult;
- db s = t * (1 + ar[i].second) / ar[i].second;
- if (s < k[i]) return false;
- if (mult > 1e40) return false;
- db now = min(k[i], cur / mult);
- k[i] -= now;
- cur -= now * mult;
- if (eq(k[i], 0)) --i;
- if (i < 0) return true;
- }
- ++day;
- if (day > m) return false;
- }
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(false);
- cout << fixed << setprecision(40);
- cin.tie(nullptr);
- #ifdef _MY
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n, m;
- int tmpt;
- db t;
- cin >> n >> m >> tmpt;
- t = tmpt;
- k.resize(n);
- ar.resize(n);
- for (auto& it : ar) {
- int a;
- cin >> a; it.first = a;
- cin >> a; it.second = a / 1000000.0;
- }
- sort(all(ar), [](pair<db, db> a, pair<db, db> b) {return a.second < b.second; });
- db l = 0;
- db r = 0;
- for (auto& it : ar) r += it.first;
- r = min(r, m * t);
- for (int i = 0; i < 100; ++i) {
- if (eq(l, r)) break;
- db mid = (l + r) / 2;
- if (check(mid, m, t)) l = mid;
- else r = mid;
- }
- cout << r;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement