#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define pb push_back
#define ld long double
using namespace std;
const int MAXN = 2e5+10;
const ld INF = 1e9+10;
typedef pair<ll,ll> pii;
void chmn(auto &a, auto b){ a = min(a, b); }
int n, k;
int p[MAXN], q[MAXN], a[MAXN], b[MAXN];
ld ans = INF;
ld dp[110][110][110];
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>k;
vector<pii> vec;
vec.pb({-1,-1});
for(int i=1; i<=n; i++){
cin>>p[i]>>q[i];
if(q[i] == -1) q[i] = MAXN;
vec.pb({q[i], i});
}
sort(vec.begin(), vec.end());
for(int i=1; i<=n; i++)
a[i] = p[vec[i].se], b[i] = q[vec[i].se];
for(int col=0; col<=k; col++){ // colab
for(int take=0; take<=col; take++) // ambil b
for(int oth=0; oth<=k-col; oth++) // ambil a
for(int i=0; i<=n; i++)
dp[i][take][oth] = INF;
dp[0][0][0] = 0;
for(int take=0; take<=col; take++){
for(int oth=0; oth<=k-col; oth++){
for(int i=1; i<=n; i++){
// gk ambil samsek
dp[i][take][oth] = dp[i-1][take][oth];
// ambil a
if(oth>=1)
chmn(dp[i][take][oth],
dp[i-1][take][oth-1] + (ld)a[i]/(col+1));
// ambil
if(take>=1)
chmn(dp[i][take][oth],
dp[i-1][take-1][oth] + (ld)b[i]/take );
}
}
}
// cout << col << ' ' << dp[n][col] << " pp\n";
chmn(ans, dp[n][col][k-col]);
}
cout << fixed << setprecision(7) << ans << '\n';
}
# | 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... |