This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
vector<pair<int, int>> s_a, s_b;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
s_a.emplace_back(a[i], i);
if (b[i] != -1) {
s_b.emplace_back(b[i], i);
}
}
sort(s_a.begin(), s_a.end());
sort(s_b.begin(), s_b.end());
long double ans = 1e9 + 7;
for (int cnt_b = 0; cnt_b <= k && cnt_b <= (int)s_b.size(); ++cnt_b) {
long double ans_nw = 0;
vector<int> used(n);
int speed = 1, cnt = 0;
for (int i = 0; i < cnt_b; ++i) {
ans_nw += s_b[i].first / (long double)speed;
cnt++;
speed++;
used[s_b[i].second] = 1;
}
for (int i = 0; i < n; ++i) {
if (cnt < k && !used[s_a[i].second]) {
ans_nw += s_a[i].first / (long double)speed;
cnt++;
used[s_a[i].second] = 1;
}
}
ans = min(ans, ans_nw);
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(25);
cout << fixed;
int t = 1;
// cin >> t;
while (t--) {
solve();
}
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... |