Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<set>
- #include<cmath>
- #include<math.h>
- #include<iomanip>
- using namespace std;
- #define int ld
- typedef long double ld;
- signed main()
- {
- cout << fixed << setprecision(10);
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int n, m, t;
- cin >> n >> m >> t;
- ld r = 0;
- vector<pair<ld, ld > > a(n);
- for (int i = 0; i < n; ++i) {
- ld s, p;
- cin >> s >> p;
- r += s;
- a[i] = make_pair(p, s);
- }
- sort(a.begin() , a.end());
- int cnt = 0;
- ld l = 0;
- vector<ld> c(n);
- while (cnt < 1000) {
- ld mid = (r + l) / 2;
- int j = 0;
- ld mid1 = mid;
- while (mid1 > 0) {
- mid1 -= a[j].second;
- c[j] = a[j].second;
- j++;
- }
- if (mid1 < 0) {
- c[j - 1] += mid1;
- j--;
- }
- for (int e = 0; e < j + 1; ++e) {
- c[e] *= (a[e].first + 1000000.0) / 1000000.0;
- }
- int k = 0;
- bool check = true;
- while (k < m && check) {
- ld t1 = t;
- while (t1 > 0 && j > -1) {
- t1 -= c[j];
- c[j] = 0;
- j--;
- }
- if (t1 < 0) {
- c[j + 1] -= t1;
- j++;
- }
- for (int e = 0; e < j + 1; ++e) {
- c[e] *= (a[e].first+1000000.0) / 1000000.0;
- }
- if (c[0] <= 0) {
- check = false;
- }
- k++;
- }
- if (c[0] <= 0) {
- l = mid;
- }
- else {
- r = mid;
- }
- cnt++;
- c.clear();
- c.resize(n);
- }
- cout << l;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement