Submission #658551

---

Source Code Expand

#include <iostream>
#include <vector>
#include <tuple>
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
typedef long double ld;
int main(){
	ll n,k;	cin>>n>>k;
	vector<ll> w(n),p(n);
	for(int i=0;i<n;i++)	cin>>w[i]>>p[i];
	vector<pair<ll,ll> > input(n);
	for(int i=0;i<n;i++)	input[i]=make_pair(p[i]*w[i],w[i]);
	//maximum sum(wi*pi)/(wi)
	//hint:内分
	ld val=0,salt=0;
	ll water=0;
	while(k--){
		vector<tuple<ld,ld,ll,int> > data;
		for(int i=0;i<(int)input.size();i++){
			ld nextsalt=salt+input[i].first;
			ll nextwater=water+input[i].second;
			data.push_back(make_tuple(nextsalt/nextwater,nextsalt,nextwater,i));
		}
		sort(data.begin(),data.end());
		reverse(data.begin(),data.end());
		int rm=get<3>(data[0]);
		val=get<0>(data[0]);
		salt=get<1>(data[0]);
		water=get<2>(data[0]);
		input.erase(input.begin()+rm);
	}
	printf("%.16Lf",val);
	return 0;
}

Submission Info

Judge Result