Advertisement
cosenza987

Untitled

Sep 30th, 2021
1,033
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     ios_base::sync_with_stdio(false);
  7.     cin.tie(0);
  8.     int n, k;
  9.     cin >> n >> k;
  10.     vector<pair<double, double>> v(n);
  11.     for(int i = 0; i < n; i++) {
  12.         cin >> v[i].first;
  13.     }
  14.     for(int i = 0; i < n; i++) {
  15.         cin >> v[i].second;
  16.     }
  17.     double ss = 0;
  18.     for(int i = 0; i < n; i++) {
  19.         ss += v[i].first * v[i].second;
  20.     }
  21.     if(k == 0) {
  22.         cout << ss << "\n";
  23.         return 0;
  24.     }
  25.     sort(v.begin(), v.end());
  26.     vector<double> prob(n), ps(n);
  27.     ps[0] = v[0].second;
  28.     prob[0] = (v[0].first * v[0].second);
  29.     for(int i = 1; i < n; i++) {
  30.         ps[i] = ps[i - 1] + v[i].second;
  31.         prob[i] = prob[i - 1] + (v[i].first * v[i].second);
  32.     }
  33.     int qnt = lower_bound(v.begin(), v.end(), make_pair(ss, 0.0)) - v.begin();
  34.     while(k--) {
  35.         while(v[qnt].first < ss) {
  36.             qnt++;
  37.         }
  38.         ss = ss * ps[qnt - 1] + (prob[n - 1] - prob[qnt - 1]);
  39.     }
  40.     cout << ss << "\n";
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement