记录编号	373284	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]货币兑换	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.542 s
提交时间	2017-02-20 17:43:13	内存使用	16.69 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100010;
const long double eps=1e-7;
void mergesort(int,int,int);
int CDQ(int,int,int);
long double getk(int,int);
long double w(int,int);
long double A[maxn],B[maxn],R[maxn],f[maxn],x[maxn],y[maxn],k[maxn];
double tmp;
int n,t[20][maxn],a[maxn],s[maxn];
int main(){
	freopen("cash.in","r",stdin);
	freopen("cash.out","w",stdout);
	scanf("%d%lf",&n,&tmp);
	f[1]=tmp;
	for(int i=1;i<=n;i++){
		scanf("%lf",&tmp);
		A[i]=tmp;
		scanf("%lf",&tmp);
		B[i]=tmp;
		scanf("%lf",&tmp);
		R[i]=tmp;
		k[i]=B[i]/A[i];
	}
	mergesort(1,n,0);
	CDQ(1,n,1);
	printf("%.3lf",(double)f[n]);
	return 0;
}
void mergesort(int l,int r,int d){
	if(l>=r){
		t[d][l]=l;
		return;
	}
	int mid=(l+r)>>1;
	mergesort(l,mid,d+1);
	mergesort(mid+1,r,d+1);
	int i=l,j=mid+1,p=l;
	while(i<=mid&&j<=r){
		if(k[t[d+1][i]]<=k[t[d+1][j]])t[d][p++]=t[d+1][i++];
		else t[d][p++]=t[d+1][j++];
	}
	while(i<=mid)t[d][p++]=t[d+1][i++];
	while(j<=r)t[d][p++]=t[d+1][j++];
}
int CDQ(int l,int r,int d){
	if(l>=r){
		a[l]=l;
		x[l]=f[l]/(A[l]*R[l]+B[l]);
		y[l]=-R[l]*x[l];
		f[l+1]=max(f[l+1],f[l]);
		return 1;
	}
	int mid=(l+r)>>1,cntl=CDQ(l,mid,d+1),i=l,j=mid+1;
	while(i<l+cntl-1&&j<=r){
		if(getk(a[i],a[i+1])-eps<k[t[d][j]])i++;
		else{
			f[t[d][j]]=max(f[t[d][j]],w(a[i],t[d][j]));
			j++;
		}
	}
	while(j<=r){
		f[t[d][j]]=max(f[t[d][j]],w(a[i],t[d][j]));
		j++;
	}
	int cntr=CDQ(mid+1,r,d+1),cnt=l-1;
	i=l;j=mid+1;
	while(i<l+cntl&&j<=mid+cntr){
		if(fabs(x[a[i]]-x[a[j]])<=eps){
			x[a[i]]=min(x[a[i]],x[a[j]]);
			j++;
		}
		else if(x[a[i]]<x[a[j]]){
			while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[i]))cnt--;
			s[++cnt]=a[i++];
		}
		else{
			while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[j]))cnt--;
			s[++cnt]=a[j++];
		}
	}
	while(i<l+cntl){
		while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[i]))cnt--;
		s[++cnt]=a[i++];
	}
	while(j<=mid+cntr){
		while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[j]))cnt--;
		s[++cnt]=a[j++];
	}
	copy(s+l,s+r+1,a+l);
	return cnt-l+1;
}
inline long double getk(int i,int j){return (y[i]-y[j])/(x[i]-x[j]);}
inline long double w(int j,int i){return f[j]*(A[i]*R[j]+B[i])/(A[j]*R[j]+B[j]);}