记录编号	108862	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]货币兑换	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.992 s
提交时间	2014-07-06 17:35:34	内存使用	5.66 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=100010;
int N;
double S;
double A[SIZEN]={0},B[SIZEN]={0},Rate[SIZEN]={0};
double f[SIZEN]={0},g[SIZEN]={0};
double ans=0;
int leftlis[SIZEN]={0},rightlis[SIZEN]={0};
void printcoor(int a){
	printf("(%lf %lf)",f[a],g[a]);
}
bool cmp_f(int a,int b){//f[a]<f[b]?
	if(f[a]==f[b]) return g[a]<g[b];
	return f[a]<f[b];
}
bool cmp_pro(int a,int b){//-A[a]/B[a]>-A[b]/B[b]?
	//即A[a]/B[a]<A[b]/B[b]
	return A[a]*B[b]<A[b]*B[a];
}
deque<int> H;//凸线
//本题中x,y坐标分别是f,g
bool under(int a,int b,int c){//b是否在ac下方
	if(f[b]==f[a]) return g[b]<=g[a];
	if(f[b]==f[c]) return g[b]<=f[c];
	double x1=f[a]-f[b],y1=g[a]-g[b];
	double x2=f[c]-f[b],y2=g[c]-g[b];
	return x1*y2-x2*y1<0;
}
void make_hull(int l,int r){//将leftlis[l~r]所含元素的凸线存在H中
	//现在leftlis[l~r]已经排序,f值递增
	H.clear();
	for(int i=l;i<=r;i++){
		while(H.size()>=2&&under(H[H.size()-2],H[H.size()-1],leftlis[i])) H.pop_back();
		H.push_back(leftlis[i]);
	}
}
double get_slope(int a,int b){//ab的斜率
	return (g[a]-g[b])/(f[a]-f[b]);
}
double maxmoney[SIZEN]={0};
void calc(int j,int i){//用j去计算并更新i的最大金钱值
	double money=f[j]*A[i]+f[j]/Rate[j]*B[i];
	ans=max(ans,money);
	maxmoney[i]=max(maxmoney[i],money);
}
void update(int l,int r){//用H中的决策更新rightlis[l~r],这是l~r的一个排列
	for(int i=l;i<=r;i++){
		double k=-A[rightlis[i]]/B[rightlis[i]];//应当把斜率不小于k的都删掉
		while(H.size()>=2&&get_slope(H[0],H[1])>=k) H.pop_front();
		calc(H[0],rightlis[i]);
	}
	for(int i=l;i<=r;i++){
		maxmoney[i]=max(maxmoney[i],maxmoney[i-1]);
		f[i]=max(f[i],maxmoney[i]*Rate[i]/(A[i]*Rate[i]+B[i]));
		g[i]=f[i]/Rate[i];
	}
}
void solve(int l,int r){
	if(l==r){
		ans=max(ans,f[l]);
		g[l]=f[l]/Rate[l];
		return;
	}
	int mid=(l+r)>>1;
	solve(l,mid);
	for(int i=l;i<=mid;i++) leftlis[i]=i;
	for(int i=mid+1;i<=r;i++) rightlis[i]=i;
	//左边序列按照f值递增排序,右边序列按照-a[i]/b[i]递减排序
	sort(leftlis+l,leftlis+mid+1,cmp_f);
	sort(rightlis+mid+1,rightlis+r+1,cmp_pro);
	make_hull(l,mid);
	update(mid+1,r);
	solve(mid+1,r);
}
void work(void){
	f[1]=S*Rate[1]/(A[1]*Rate[1]+B[1]);
	g[1]=f[1]/Rate[1];
	maxmoney[0]=maxmoney[1]=S;
	solve(1,N);
	printf("%.3lf\n",ans);
}
void read(void){
	scanf("%d",&N);
	scanf("%lf",&S);
	ans=S;
	for(int i=1;i<=N;i++) scanf("%lf%lf%lf",&A[i],&B[i],&Rate[i]);
}
int main(){
	freopen("cash.in","r",stdin);
	freopen("cash.out","w",stdout);
	read();
	work();
	return 0;
}