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>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 500 + 9;
const ll inf = 1e18 + 7;
ld ans = inf*1.0,dp[N][N];
ll n,k,collab;
LL a[N];
bool lf(LL x,LL y){
return x.sc < y.sc;
}
ld cal(ll mid){
for (ll i = 1;i <= n;i++)
for (ll j = 0;j <= i;j++){
dp[i][j] = inf;
if (i - j - 1 >= mid) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + (ld)a[i].sc/((ld)i - j);
if (j) dp[i][j] = min(dp[i][j],dp[i - 1][j - 1] + (ld)a[i].fs/((ld)mid + 1));
}
ld tmp = inf;
for (ll i = k - mid;i <= n;i++)
if (n - i >= mid) tmp = min(tmp,dp[n][i]);
return tmp;
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
}
cin>>n>>k;
for (ll i = 1;i <= n;i++){
cin>>a[i].fs>>a[i].sc;
collab += (a[i].sc != -1);
if (a[i].sc == -1) a[i].sc = inf;
}
sort(a + 1,a + n + 1,lf);
for (ll i = 0;i < min(k,collab);i++) ans = min(ans,cal(i));
cout<<fixed<<setprecision(6)<<ans; return 0;
ll l = 0,h = min(k,collab);
while(l <= h){
ll mid = (l + h)/2;
if (cal(mid) < cal(mid + 1)) h = mid - 1;
else l = mid + 1;
}
//debug(h);
cout<<fixed<<setprecision(6)<<cal(l);
}
/// be confident
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |