记录编号	478430	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]货币兑换	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	0.777 s
提交时间	2017-12-11 16:58:25	内存使用	7.16 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define N 100010
#define db double
#define inf 0x7fffffff
#define sign(a) (((a)>-eps)-((a)<eps))
int n,top,sta[N],id[N],tmp[N],idk[N],tmpk[N],match[N];
db ans[N],ak[N],bk[N],rate[N],f[N],g[N];
inline db max(db a,db b){return a>b?a:b;}
inline bool comp(const int &a,const int &b)
	{return f[a]<f[b] || ( sign(f[a]-f[b])==0&&g[a]<g[b] );}
inline double k(int a,int b)
{
	if(sign(f[a]-f[b])==0)return sign(g[a]-g[b])*inf;
	return (g[a]-g[b])/(f[a]-f[b]);
}
inline bool compk(const int &a,const int &b)
	{return sign( (-ak[a]/bk[a]) - (-ak[b]/bk[b]) ) >0 ;}
inline void CDQ(int l,int r)
{
	if(l==r){g[l]=f[l]/rate[l];return;}
	register int hd1,i,t,mi=l+r>>1,p=l-1,q=mi,h=l-1;
	for(i=l;i<=r;++i)
		if(match[idk[i]]<=mi)tmpk[++p]=idk[i];
		else tmpk[++q]=idk[i];
	for(i=l;i<=r;++i)idk[i]=tmpk[i];
	CDQ(l,mi);
	for(top=0,i=l;i<=mi;++i)
	{
		while(top>1 && k(sta[top-1],sta[top]) < k(sta[top],id[i]) )--top;//****
		sta[++top]=id[i];
	}
	for(hd1=1,i=mi+1;i<=r;++i)
	{
		t=match[idk[i]];
		while(  hd1<top&&sign(  k(sta[hd1],sta[hd1+1]) - (-ak[t]/bk[t]) ) >=0  )++hd1;
		ans[t]=max(ans[t],f[sta[hd1]]*ak[t]+g[sta[hd1]]*bk[t]);
	}
	for(i=mi+1;i<=r;++i)
		t=match[idk[i]],ans[t]=max(ans[t],ans[t-1]),f[t]=ans[t]*rate[t]/(ak[t]*rate[t]+bk[t]);
	CDQ(mi+1,r);
	p=l,q=mi+1,h=l;
	while(p<=mi&&q<=r)
		if(comp(id[p],id[q]))tmp[h++]=id[p++];
		else tmp[h++]=id[q++];
	while(p<=mi)tmp[h++]=id[p++];
	while(q<=r)tmp[h++]=id[q++];
	for(i=l;i<=r;++i)id[i]=tmp[i];

}
int main()
{
	// freopen("Ark.in","r",stdin);
	freopen("cash.in","r",stdin);
	freopen("cash.out","w",stdout);
	register int i,j;
	scanf("%d%lf",&n,&ans[1]);
	for(i=1;i<=n;++i)
		scanf("%lf%lf%lf",&ak[i],&bk[i],&rate[i]);
	f[1]=ans[1]*rate[1]/(ak[1]*rate[1]+bk[1]);
	for(i=1;i<=n;++i)id[i]=idk[i]=match[i]=i;
	sort(match+1,match+n+1,compk);
	CDQ(1,n);
	printf("%.3f\n",ans[n]);
}