记录编号	188397	评测结果	AAAAAAAATTTTTTTTTTTT
题目名称	[NOI 2012]骑行川藏	最终得分	40
用户昵称	四季木哥	是否通过	未通过
代码语言	C++	运行时间	12.002 s
提交时间	2015-09-23 07:28:04	内存使用	0.54 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
double v[10050], T, Eu, k[10050], s[10050], n;
double solve(int L, int R, double E) {
    if(L == R) {
        double v0 = sqrt(E/(k[L]*s[L]))+v[L];
	    T = s[L]/v0;
	    if(T < 0) T = INF;
	    return T;
	} 
	double l = 0, r = E;
    while(1) {
       int M = L + (R-L)/2;
	   double mid = l + (r-l)/2; 
	   double midmid1 = l+(mid-l)/2, midmid2 = mid+(r-mid)/2;
	   double x = solve(L, M, midmid1) + solve(M+1, R, E-midmid1);
	   double y = solve(L, M, midmid2) + solve(M+1, R, E-midmid2);
	   if(x > y) l = midmid1; else r = midmid2;
	   if(abs(x-y) < 0.00000001) return min(x, y);
	}
}

int main() {
	freopen("bicycling.in", "r", stdin);
	freopen("bicycling.out", "w", stdout);
    cin >> n >> Eu;
    for(int i = 0; i < n; i++) cin >> s[i] >> k[i] >> v[i];
    double ans = solve(0, n-1, Eu);
    printf("%.7f", ans);
return 0;
}