记录编号	390320	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]货币兑换	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	1.381 s
提交时间	2017-04-02 17:52:12	内存使用	6.01 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n;double A[maxn],B[maxn],Rate[maxn],f[maxn],g[maxn],hav[maxn];
int L[maxn],R[maxn],q[maxn];
void Rabit_in(){
	scanf("%d%lf",&n,&hav[1]);
	for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&A[i],&B[i],&Rate[i]);
	f[1]=hav[1]/(A[1]+B[1]/Rate[1]);
}
bool Cmpf(int a,int b){return f[a]<f[b];}
bool Cmpab(int a,int b){return A[a]/B[a]<A[b]/B[b];}
double Get(int i,int j){return (g[i]-g[j])/(f[i]-f[j]);}
bool Dig(int a,int b,int c){
	if(f[a]==f[b])return g[b]<=g[a];
	return Get(b,a)<=Get(c,a);
}
void Rabit_run(int l,int r){
	if(l==r){g[l]=f[l]/Rate[l];return;}
	int mid=(l+r)>>1,i,cnt1=0,cnt2=0,s=1,t=0;double x,tmp;
	Rabit_run(l,mid);
	for(i=l;i<=mid;i++)L[cnt1++]=i;sort(L,L+cnt1,Cmpf);
	for(i=mid+1;i<=r;i++)R[cnt2++]=i;sort(R,R+cnt2,Cmpab);
	for(i=0;i<cnt1;i++){
		while(s<t&&Dig(q[t-1],q[t],L[i]))t--;
		q[++t]=L[i];
	}
	for(i=0;i<cnt2;i++){
		x=-A[R[i]]/B[R[i]];
		while(s<t&&Get(q[s+1],q[s])>=x)s++;
		tmp=f[q[s]]*A[R[i]]+f[q[s]]*B[R[i]]/Rate[q[s]];
		hav[R[i]]=max(hav[R[i]],tmp);
	}
	for(i=mid+1;i<=r;i++)
		hav[i]=max(hav[i],hav[i-1]),f[i]=max(f[i],hav[i]/(A[i]+B[i]/Rate[i]));
	Rabit_run(mid+1,r);
}
int main(){
	freopen("cash.in","r",stdin);freopen("cash.out","w",stdout);
	Rabit_in();Rabit_run(1,n);
	printf("%.3f\n",hav[n]);
	fclose(stdin);fclose(stdout);return 0;
}