记录编号	478271	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]货币兑换	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	1.709 s
提交时间	2017-12-10 11:54:05	内存使用	9.85 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 100005
using namespace std;
struct data{int id;double a,b,ak,bk,k;}d[N],tmp[N];
bool cmpxy(data a,data b){return (a.b==b.b)?(a.a<b.a):(a.b<b.b);}
bool cmpid(data a,data b){return a.id<b.id;}
bool cmpk(data a,data b){return -a.bk/a.ak>-b.bk/b.ak;}
int n,s,q[N],top;
double f[N];
double slope(int x,int y){
	if(fabs(d[y].b-d[x].b)<1e-7)return 0x7fffffff;
	return (d[y].a-d[x].a)/(d[y].b-d[x].b);
}
void cdq(int l,int r){
	if(l==r){
		f[d[l].id]=max(f[d[l].id-1],f[d[l].id]);
		d[l].b=f[l]/(d[l].k*d[l].ak+d[l].bk);
		d[l].a=d[l].k*d[l].b;
		return ;
	}
	int mid=(l+r)>>1,l1=l,l2=mid+1;
	for(int i=l;i<=r;i++){
		if(d[i].id<=mid)tmp[l1++]=d[i];
		else tmp[l2++]=d[i];
	}
	for(int i=l;i<=r;i++)d[i]=tmp[i];
	cdq(l,mid);
	top=0;
	sort(d+l,d+mid+1,cmpxy);
	for(int i=l;i<=mid;i++){
		while(top&&slope(q[top-1],q[top])<slope(q[top],i))top--;
		q[++top]=i;
	}
	for(int i=mid+1,now=1;i<=r;i++){
		while(now<top&&slope(q[now],q[now+1])>(-d[i].bk/d[i].ak))now++;
		if(d[q[now]].a*d[i].ak+d[q[now]].b*d[i].bk>f[d[i].id]){
			f[d[i].id]=d[q[now]].a*d[i].ak+d[q[now]].b*d[i].bk;
			d[i].b=f[d[i].id]/(d[i].k*d[i].ak+d[i].bk);
			d[i].a=d[i].k*d[i].b;
		}
	}
	cdq(mid+1,r);
}
int main(){
	freopen("cash.in","r",stdin);
	freopen("cash.out","w",stdout);
	scanf("%d%d",&n,&s);
	f[0]=s;
	for(int i=1;i<=n;i++){
		double a,b,c;
		scanf("%lf%lf%lf",&a,&b,&c);
		d[i]=(data){i,0,0,a,b,c};
	}
	sort(d+1,d+n+1,cmpk);
	cdq(1,n);
	sort(d+1,d+n+1,cmpid);
	printf("%0.3lf\n",f[n]);
	return 0;
}
//f[x] is most money
//a[x] is most A
//b[x] is most B
//K*b*ak+b*bk=f
//b=f/(K*ak+bk)
//a=Kf/(K*ak+bk)
//f[i]=max(a[j]*(ak[i]-ak[j])+b[j]*(bk[i]-bk[j]))
//b[j]>b[k] && j>>k
//a[j]*ak[i]+b[j]*bk[i]>a[k]*ak[i]+b[k]*bk[i]
//(a[j]-a[k])*ak[i]+(b[j]-b[k])*bk[i]>0
//(a[j]-a[k])*ak[i]>(b[j]-b[k])*(-bk[i])
//(a[j]-a[k])/(b[j]-b[k])>-bk[i]/ak[i]