# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
678428 | Pacybwoah | Let's Win the Election (JOI22_ho_t3) | C++14 | 0 ms | 0 KiB |
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<iostream>#include<vector>#include<iomanip>#include<utility>#include<algorithm>#define ld long doubleusing namespace std;vector<pair<ld,ld>> vec;int n,k;ld solve(int m){vector<vector<ld>> dp(n+1,vector<ld>(k-m+1,1e9+7));dp[1][0]=(m>0?vec[1].first:0);if(k-m>0) dp[1][1]=vec[1].second;for(int i=2;i<=n;i++){for(int j=0;j<=min(k-m,i);j++){dp[i][j]=min(dp[i][j],dp[i-1][j]+(i-j>m?0:vec[i].first/float(i-j)));if(j>0) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+vec[i].second/float(m+1));}}/*for(int i=1;i<=n;i++){for(int j=0;j<=k-m;j++) if(m==2) cout<<dp[i][j]<<" ";cout<<"\n";}*/return dp[n][k-m];}int main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>k;vec.resize(n+1);for(int i=1;i<=n;i++) cin>>vec[i].second>>vec[i].first;for(int i=1;i<=n;i++) if(vec[i].first==-1) vec[i].first=1e9;sort(next(vec.begin()),vec.end());int l=0,r=k;ld ans=1e9+7;while(l<r){int mid=(l+r)>>1;ld a=solve(max(mid,0)),b=solve(min(mid+1,r));ans=min(ans,min(a,b));if(a>b) l=min(mid+1,r);else r=(max(mid,0));}for(int i=0;i<=k;i++) ans=min(solve(i),ans);cout<<fixed<<setprecision(12)<<ans;}