#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
const double INF = 1e18;
int main() {
int n, k;
cin >> n >> k;
vector<pair<double, double>> states;
for (int i = 0; i < n; i++) {
double a, b;
cin >> a >> b;
if (b == -1) b = INF;
states.push_back({a, b});
}
sort(states.begin(), states.end(), [](const pair<double, double> &p1, const pair<double, double> &p2) {
return p1.second < p2.second;
});
double ans = INF;
for (int m = 0; m <= min(n, k); m++) {
if (m > 0 && states[m-1].second >= INF) {
break;
}
double time_collab = 0.0;
for (int i = 0; i < m; i++) {
time_collab += states[i].second / (i + 1);
}
vector<double> a_remaining;
for (int i = m; i < n; i++) {
a_remaining.push_back(states[i].first);
}
if (a_remaining.size() < k - m) {
continue;
}
sort(a_remaining.begin(), a_remaining.end());
double sum_vote = 0.0;
for (int i = 0; i < k - m; i++) {
sum_vote += a_remaining[i];
}
double time_vote = sum_vote / (m + 1);
ans = min(ans, time_collab + time_vote);
}
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |