# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
676683 | owoovo | Let's Win the Election (JOI22_ho_t3) | C++17 | 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<bits/stdc++.h>
#define ll long long
using namespace std;
struct pp{
int f,s;
};
operator<(pp a,pp b){
return a.f==b.f?a.s>b.s:a.f<b.f;
}
multiset<pair<int,int>> a;
multiset<pp> b,c;
long double ans=10000000000;
int main(){
ll n,k;
cin>>n>>k;
for(ll i=0;i<n;i++){
int x,y;
cin>>x>>y;
a.insert(make_pair(x,y));
if(y!=-1){
pp u;
u.f=y;
u.s=x;
b.insert(u);
}
}
for(ll i=0;;i++){
long double nowans=0;
int nowc=1;
for(auto r:c){
long double x=r.f;
nowans+=x/nowc;
nowc++;
}
multiset<pair<int,int>>::iterator s=a.begin();
for(ll j=i;j<k;j++){
pair<int,int> u=*s;
long double x=u.first;
nowans+=x/nowc;
s++;
}
ans=min(ans,nowans);
if(b.size()==0){
break;
}else{
pp u=*b.begin();
c.insert(u);
a.erase(a.find(make_pair(u.s,u.f)));
b.erase(b.begin());
}
}
cout<<fixed<<ans<<'\n';
return 0;
}