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;
typedef long double ld;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 505;
const ld inf = 1e12;
vector<ld> suff[N];
ld A[N];
ld B[N];
ld dp[N][N];
void mini(ld &a, ld b){
a = min(a, b);
}
int main(){
fastIO;
//freopen("in.txt","r",stdin);
int n, k;
cin >> n >> k;
vector<pair<ld,ld>> C(n);
for(int i = 0 ; i < n; i ++ ){
cin >> C[i].se >> C[i].fi;
if(C[i].fi == -1) C[i].fi = inf;
}
sort(C.begin(), C.end());
for(int i = 0 ; i < n; i ++ ){
A[i + 1] = C[i].se;
B[i + 1] = C[i].fi;
}
for(int i = n; i >= 1; i -- ){
for(int j = i ; j <= n; j ++ ){
suff[i].push_back(A[j]);
}
sort(suff[i].begin(), suff[i].end());
}
ld res = inf;
ld current;
for(int take = 0; take <= k ; take ++ ){
for(int i = 0 ; i <= n; i ++ ){
for(int j = 0 ; j <= n; j ++ ){
dp[i][j] = inf;
}
}
dp[0][0] = 0;
for(int i = 1; i <= n; i ++ ){
for(int j = 0 ; j <= i ; j ++ ){
if(dp[i - 1][j] == inf) continue;
mini(dp[i][j], dp[i-1][j] + A[i] / ld(take + 1));
mini(dp[i][j+1], dp[i-1][j] + B[i] / ld(j + 1));
}
}
for(int id = take; id <= k; id ++ ){
current = dp[id][take];
for(int j = 0 ; j < k - id; j ++ ){
current += suff[id + 1][j] / ld(take + 1);
}
res = min(res, current);
}
}
cout << fixed << setprecision(9) << res << "\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... |