#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;
int n,k;
ll a[501],b[501];
ll dp[501][501];
int per[501];
ll cal(int m){
int x=k-m;
for(int i=0;i<=n;i++){
for(int j=0;j<=x;j++){
dp[i][j]=1e11;
}
}
dp[0][0]=0;
ll res=1e11;
for(int i=1;i<=n;i++){
for(int j=0;j<=x;j++){
if(j>i)continue;
if(j){
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[per[i]]/(m+1)));
}
if(i!=j){
if(b[per[i]]>0&&i-j<=m)dp[i][j]=min(dp[i][j],dp[i-1][j]+(b[per[i]]/(i-j)));
else if(i-j>m)dp[i][j]=min(dp[i][j],dp[i-1][j]);
}
}
if(i>=k){
res=min(res,dp[i][x]);
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>k;
int m=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
a[i]*=10000;
b[i]*=10000;
if(b[i]!=-10000)m++;
}
iota(per+1,per+n+1,1);
sort(per+1,per+n+1,[&](const int &x,const int &y){
if(b[x]==-10000)return false;
if(b[y]==-10000)return true;
return b[x]<b[y];
});
double ans=1e11;
for(int i=0;i<=min(m,k);i++){
ans=min(ans,double(cal(i)));
}
cout<<ans/10000;
}
# | 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... |