Advertisement
cosenza987

Untitled

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