#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin(".in");
//ofstream cout(".out");
//iterate over number of collaborators (c) to take
//take vote if voters < k - c
//sort by vote cost, divide by c+1
//but collaborator order will not be optimal! (has to be in increasing collaboration cost)
//what if we sort by collaborator cost?
//we can still iterate over c, but use dp[i][j] where i = index and j = #collaborators taken, value is minimum cost for the collaborators + voters
//then for each j from c to k, we need to calculate the array suffix (j, n) -> can precompute
//dp[i][j] = min(dp[i-1][j] + a[i] / (c+1), dp[i-1][j-1] + b[i] / j)
in2(n,k);
vector<double> a;
vector<double> b;
f0r(i,n){
in2(x,y);
if(y == -1)y = 4e18;
a.pb(x);
b.pb(y);
}
vector<pair<double,double>> x;
f0r(i,n){
x.pb(mp(b[i],a[i]));
}
sort(all(x));
f0r(i,n){
b[i] = x[i].first;
a[i] = x[i].second;
}
vvi suf(n+1, vi(n+1));
vi thing;
for(int i = n-1; i>=0; i--){
thing.pb(a[i]);
sort(all(thing));
int sum = 0;
f0r(j, thing.size()){
sum += thing[j];
suf[i][j+1] = sum;
}
}
double ans = 4e18;
for(double c = 0; c<n+1; c++){
vector<vector<double>> dp(n, vector<double>(n+1, 4e18));
dp[0][0] = a[0] / (c+1);
dp[0][1] = b[0];
FOR(i,1,n){
dp[i][0] = dp[i-1][0] + a[i] / (c+1);
FOR(j, 1, n+1){
dp[i][j] = min(dp[i-1][j] + a[i] / (c+1), dp[i-1][j-1] + b[i] / j);
}
}
double anss = 4e18;
for(int j = c-1; j<k; j++){
double thing;
if(j == -1)thing = 0;
else thing = dp[j][c];
if(c == 0){
// dout2(suf[j+1][k-c-(j+1-c)],thing);
}
anss = min(anss, suf[j+1][k - c - (j + 1 - c)] / (c + 1) + thing);
}
// dout(anss);
ans = min(ans, anss);
}
cout<<fixed;
cout<<setprecision(17);
out(ans);
}
# | 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... |