记录编号	266979	评测结果	AAAAAAAAAA
题目名称	16.[NOI 2007]货币兑换	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.536 s
提交时间	2016-06-10 15:53:42	内存使用	9.01 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 120000
#define eps 1e-9
#define inf 1e9
using namespace std;
int fa[maxn],ch[maxn][2];
double f[maxn],x[maxn],y[maxn],lk[maxn],rk[maxn],a[maxn],b[maxn],rate[maxn];
int n,m,rot,num;

double fabs(double x){
    return (x>0)?x:-x;
}

inline void zigzag(int x,int &rot){
    int y=fa[x],z=fa[y];
    int p=(ch[y][1]==x),q=p^1;
    if (y==rot) rot=x;
        else if (ch[z][0]==y) ch[z][0]=x; else ch[z][1]=x;
    fa[x]=z; fa[y]=x; fa[ch[x][q]]=y;
    ch[y][p]=ch[x][q]; ch[x][q]=y; 
}

inline void splay(int x,int &rot){
    while (x!=rot){
        int y=fa[x],z=fa[y];
        if (y!=rot)
            if ((ch[y][0]==x)xor(ch[z][0]==y)) zigzag(x,rot); else zigzag(y,rot);
        zigzag(x,rot);
    }
}

inline void insert(int &t,int anc,int now){
    if (t==0){
        t=now;
        fa[t]=anc;
        return ;
    }
    if (x[now]<=x[t]+eps) insert(ch[t][0],t,now);
    else insert(ch[t][1],t,now);
}

inline double getk(int i,int j){
    if (fabs(x[i]-x[j])<eps) return -inf;
    else return (y[j]-y[i])/(x[j]-x[i]);
}

inline int prev(int rot){
    int t=ch[rot][0],tmp=t;
    while (t){
        if (getk(t,rot)<=lk[t]+eps) tmp=t,t=ch[t][1];
        else t=ch[t][0];
    }
    return tmp;
}
inline int succ(int rot)//求可以和当前点组成凸包的左边第一个点
{
    int t=ch[rot][1],tmp=t;
    while(t){
        if(getk(rot,t)+eps>=rk[t]) tmp=t,t=ch[t][0];
        else t=ch[t][1];
    }
    return tmp;
}

inline void update(int t){
    splay(t,rot);
    if (ch[t][0]){
        int left=prev(rot);
        splay(left,ch[rot][0]); ch[left][1]=0;
        lk[t]=rk[left]=getk(left,t);
    }
    else lk[t]=inf;
    if (ch[t][1]){
        int right=succ(rot);
        splay(right,ch[rot][1]); ch[right][0]=0;
        rk[t]=lk[right]=getk(t,right);
    }
    else rk[t]=-inf;
    if (lk[t]<=rk[t]+eps)//在原凸包内部的情况，直接删掉该点 
    {
        rot=ch[t][0]; ch[rot][1]=ch[t][1]; fa[ch[t][1]]=rot; fa[rot]=0;
        lk[rot]=rk[ch[t][1]]=getk(rot,ch[t][1]);
    }
}        

inline int find(int t,double k)//找到当前斜率的位置，即找到最优值
{
    if (t==0) return 0;
    if (lk[t]+eps>=k&&k+eps>=rk[t]) return t;
    if (k+eps>lk[t]) return find(ch[t][0],k);
    else return find(ch[t][1],k);
}

int main(){
    freopen("cash.in","r",stdin);
    freopen("cash.out","w",stdout);
    scanf("%d%lf",&n,&f[0]);
    for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]);
    for(int i=1;i<=n;i++){
        int j=find(rot,-a[i]/b[i]);
        f[i]=max(f[i-1],x[j]*a[i]+y[j]*b[i]);
        y[i]=f[i]/(a[i]*rate[i]+b[i]);
        x[i]=y[i]*rate[i];
        insert(rot,0,i);
        update(i);
    }
    printf("%.3lf\n",f[n]);
    return 0;
}