记录编号	451825	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	964.[NOI 2012]骑行川藏	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	2.365 s
提交时间	2017-09-18 13:58:26	内存使用	0.63 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#define ld long double
const ld INF = 1e10;
const ld eps = 1e-12;
using namespace std;

const int MAXN = 10005;

int N;
ld E, S[MAXN], K[MAXN], V[MAXN], Ans = INF;
inline ld sqr(ld x) { return x * x; }

namespace bin {
	int idx; ld lambda;
	inline ld Fn(ld v) {
		return lambda * K[idx] * v * v * (v - V[idx]) * 2.0 + 1.0;
	}
	inline ld solve(ld L, ld R) {
		ld M;
		while(R - L > eps) {
			M = (L + R) / 2.0;
			if(Fn(M) >= 0.0) L = M; else R = M;
		}
		return L;
	}
}

inline bool ok(ld lambda) {
	ld v, e = 0, CurAns = 0;

	int i;
	bin::lambda = lambda;
	for(i = 1; i <= N; i++) {
		bin::idx = i;

		v = bin::solve(max((ld)0.0, V[i]), INF);
		CurAns += S[i] / v;
		e += K[i] * sqr(V[i] - v) * S[i];
	}
	if(e <= E) { Ans = min(Ans, CurAns); return 1; }
	return 0;
}

int main() {
	freopen("bicycling.in", "rt", stdin);
	freopen("bicycling.out", "wt", stdout);

	int i;
	scanf("%d%Lf", &N, &E);
	for(i = 1; i <= N; i++) scanf("%Lf%Lf%Lf", &S[i], &K[i], &V[i]);
	ld L = -INF, R = 0, M;
	while(R - L > eps) {
		M = (L + R) / 2;
		if(ok(M)) L = M; else R = M;
	}
	printf("%.8Lf", Ans);
}