#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera
#define ld long double
#define ll long long
typedef pair<ld,ld> pii;
#define f first
#define s second
#define lc 2*id
#define rc 2*id+1
#define all(x) x.begin(),x.end()
#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" ) ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" ) ";return "";}
const int L = 500+10,mod = 1e9+7;
const int inf = 1e9+10;
int n,k;
pii inp[L];
ld a[L],b[L];
ld dp[2][L][L];
ld ans = inf;
vector<ld> sf;
int main(){
//ofstream cout ("out.out");
//ifstream cin ("in.in");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>inp[i].s>>inp[i].f;
if(inp[i].f == -1){
inp[i].f = inf;
}
}
sort(inp+1,inp+n+1);
for(int i=1;i<=n;i++){
a[i] = inp[i].s;
b[i] = inp[i].f;
}
for(int i=0;i<=k;i++){
dp[0][0][k] = 0;
}
for(int i=1;i<=k;i++){
for(int j=0;j<=k;j++){
dp[0][i][j] = inf;
}
}
sf.clear();
for(int i=1;i<=n;i++){
sf.pb(a[i]);
}
sort(all(sf));
ans = 0;
for(int i=0;i<k;i++){
ans += sf[i];
}
for(int i=1;i<=k;i++){
int id = i%2;
for(int j=0;j<=k;j++){
for(int h=0;h<=k;h++){
dp[id][j][h] = dp[!id][j][h]+a[i]/(h+j+1);
if(j != 0 and h != k){
dp[id][j][h] = min(dp[id][j][h], dp[!id][j-1][h+1] + b[i]/j);
}
}
}
sf.clear();
for(int j=i+1;j<=n;j++){
sf.pb(a[j]);
}
sort(all(sf));
ld sum = 0;
for(int j=0;j+1+i<=k;j++){
sum += sf[j];
}
for(int j=0;j<=k;j++){
ans = min(ans,dp[id][j][0] + sum/(j+1));
}
}
cout<<setprecision(10)<<fixed<<ans<<endl;
}
# | 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... |