Submission #1320873

#TimeUsernameProblemLanguageResultExecution timeMemory
1320873ghos007Let's Win the Election (JOI22_ho_t3)C++20
10 / 100
6 ms436 KiB
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int INF = 1e18;
const int mod = 1e9+7;
ld cost(int cnt_users,vector <pair<int,int>> &free,int need) {
  ld ans = 0;
  sort(free.begin(),free.end());
  for (int i = 0;i < need;i++) {
    ans += free[i].first / (cnt_users * 1.0l);
  }
  return ans;
}
signed main() {
  mt19937 rng(69);
  int n,k;
  cin >> n >> k;
  vector <pair<int,int>> vec(n);
  vector <pair<int,int>> govno,good;
  for (int i = 0;i < n;i++) {
    cin >> vec[i].first >> vec[i].second;
    if (vec[i].second == -1) {
      govno.push_back(vec[i]);
    }else {
      good.push_back(vec[i]);
    }
  }
  sort(good.begin(),good.end(),[&] (pair<int,int> a,pair<int,int> b) {
    return a.second < b.second;
  });
  ld best = INF;
  for (int cnt_support = 0;cnt_support <= good.size();cnt_support++) {
    vector <pair<int,int>> tmp;
    for (auto el : govno) {
      tmp.push_back(el);
    }
    ld ans = 0;
    for (int i = 0;i < cnt_support;i++) {
      ans += (good[i].second) / ((1 + i) * 1.0l);
    }
    for (int i = cnt_support;i < good.size();i++) {
      tmp.push_back(good[i]);
    }
    ans += cost(cnt_support + 1,tmp,max(0ll,k - cnt_support));
    best = min(best,ans);
  }
  cout << fixed << setprecision(15) << best << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...