This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld
#define int ll
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(10);
int n, k; cin >> n >> k;
vector<pair<int, int>> a(n);
int C = 0;
f(i, 0, n) {
cin >> a[i].ff >> a[i].sc;
C += (a[i].sc == -1);
}
sort(all(a), [](pii a, pii b) {
if (a.sc == -1) return false;
if (b.sc == -1) return true;
if (a.sc != b.sc) return a.sc < b.sc;
return a.ff > b.ff;
});
//for (auto& u : a) cout << u.ff << ' ' << u.sc << '\n';
double ans = 1e18;
f(i, 0, min(k, n - C) + 1) {
double cur = 0;
for (int j = 0; j < i; j++) {
cur += double(a[j].sc) / double(j + 1);
}
int cnt = i + 1;
vector<pair<int, int>> ost;
f(j, i, n) ost.pb(a[j]);
sort(all(ost));
f(j, 0, k - i) {
cur += (double)(ost[j].ff) / (double)cnt;
}
ans = min(cur, ans);
}
cout << ans << '\n';
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... |