Submission #1248007

---

Source Code Expand

#include<iostream>
#include<algorithm>
using namespace std;
typedef long double Ld;
#define INF 1e9+9

Ld w[1111], p[1111],y[1111];
int k, n;

bool C(Ld x) {
	for (int i = 0; i < n; i++) {
		y[i] = p[i] - x*w[i];
	}
	sort(y, y + n);
	Ld sum = 0;
	for (int i = 0; i < k; i++)sum += y[n - 1 - i];
	return sum >= 0;
}
int main() {
	cin >> k >> n;
	for (int i = 0; i < n; i++)cin >> w[i] >> p[i];
	for (int i = 0; i < n; i++)p[i] = w[i] / 100 * p[i];

	Ld lb = 0, ub = INF;
	for (int i = 0; i < 300; i++) {
		Ld mid = (lb + ub) / 2;
		if (C(mid))lb = mid;
		else ub = mid;
	}
	printf("%.13Lf\n", ub*100);
	getchar();
	getchar();
	return 0;
}

Submission Info

Judge Result