[NOI 2007]通貨をCashに両替する

/*
書き終わったらSTLを使っている牛がいます.BZOJでACができます.
http://hi.baidu.com/wwwaaannngggrs/blog/item/e536b809c5b533d23bc763ca.html
*/
この問題は非常に典型的な傾斜最適化で、卵の痛いところはxが単調ではなく、Splayで守らなければならないことにあります.
方程式はf[i]=max(f[i-1],a[i]*x[j]+b[i]*y[j](j∈[1,n-1])//x[i],y[i]はf[i]で最適値を取った場合、i番目の日にa券とb券の数を得ることができるという意味です.
暴力のO(n^2)アルゴリズムは比較的裸です./私は最初に暴力の検証の正確性を書きました.
ただし、極限データは10 w、O(n^2)は過ぎません.
そしてこの問題は傾きを最適化することができます.
式子を改作する
-a[i]*x[j]+f[i]=b[i]*y[j]
-a[i]/b[i]*x[j]+f[i]=y[j]
傾きは-a[i]/b[i]です.最大のスクリーンショットを求めます.
上部の凸殻を維持するのに相当します.
問題はこの式のx、つまりx[i]は単調ではないです.毎日獲得できるa券の数は単調に増加するとは限りません.
じゃ、xについてスピリットを作ります.
そして毎回現在の直線に対する最適値を探す時
現在の直線が接触できる一番目の点は必ずこのような性質を満たすからです.
この点とその左の点の直線の傾きは現在の直線より大きいです.
この点とその右の点の直線の傾きは現在の直線より小さいです.
Splayではこの点と左の点の傾きを維持し、右の店の傾きを維持します.
ロゴの時間に最適な意思決定を見つけることができます.
挿入するとその位置に挿入すべきです.挿入してからSplayをルートに入れます.
左の凸殻をそれぞれ維持し、右の凸殻/具体的な作り方はコードの中にあります.
/*
この問題は非常に怪しいです.私は本機でcenaとNOI 07の公式データを使って測定した時はACで、使う時は2.5 sぐらいで、fastioを使う時は1 s以下です.
しかしBZOJとTWのOJに渡します.この二つはlinuxをプラットフォームとしているOJがTLEを落とします.定数の問題ではないと確定できます.fastioもそうです.
windowsとlinuxはまたどこかの卵が痛いかもしれません.コンピュータにlinuxがないので、このようにしましょう.時間があればlinuxの下で見てください.
*/

//Lib
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
//Macro
#define rep(i,a,b) for(int i=a,tt=b;i<=tt;++i)
#define rrep(i,a,b) for(int i=a,tt=b;i>=tt;--i)
#define erep(i,e,x) for(int i=x;i;i=e[i].next)
#define irep(i,x) for(__typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define read() (strtol(ipos,&ipos,10))
#define sqr(x) ((x)*(x))
#define pb push_back
#define PS system("pause");
typedef long long ll;
typedef pair<int,int> pii;
const int oo=~0U>>1;
const double inf=1e20;
const double eps=1e-6;
string name="cash",in=".in",out=".out";
//Var
int n,root;double s;
double a[100008],b[100008],r[100008];
double f[100008];
long long base[20];
char Input[10000008],*ipos;
struct T
{
	int lc,rc,fa;
	double lk,rk,x,y;
	#define lc(t) tree[t].lc
	#define rc(t) tree[t].rc
	#define fa(t) tree[t].fa
	#define x(t) tree[t].x
	#define y(t) tree[t].y
	#define lk(t) tree[t].lk
	#define rk(t) tree[t].rk
}tree[100008];
inline double getreal()
{
	int x=0,z=0;char c;
	long long y=0;
	while (*ipos<=32) ipos++;
	while (1)
	{
		c=*ipos++; if (c<=32) return x;
		if (c<48) break;
		x=(x<<3)+(x<<1)+c-48;
	}
	while (1)
	{
		c=*ipos++; if (c<=32) return x+double(y)/base[z];
		y=(y<<3)+(y<<1)+c-48;
		z++;
	}
}
void Zig(int x)
{
	int y=fa(x),z=fa(y);
	if(lc(z)==y)lc(z)=x;else rc(z)=x;fa(x)=z;
	fa(rc(x))=y;lc(y)=rc(x);fa(y)=x;rc(x)=y;
}
void Zag(int x)
{
	int y=fa(x),z=fa(y);
	if(lc(z)==y)lc(z)=x;else rc(z)=x;fa(x)=z;
	fa(lc(x))=y;rc(y)=lc(x);fa(y)=x;lc(x)=y;	
}
void Splay(int x,int &goal)
{
	int ff=fa(goal);
	for(int y,z;fa(x)!=ff;)
	{
		y=fa(x);z=fa(y);
		if(z==ff)
			if(lc(y)==x)Zig(x);
			else Zag(x);
		else
			if(lc(z)==y)
				if(lc(y)==x)Zig(y),Zig(x);
				else Zag(x),Zig(x);
			else
				if(rc(y)==x)Zag(y),Zag(x);
				else Zig(x),Zag(x);
	}
	goal=x;
}
double CalcY(int i){return f[i]/(r[i]*a[i]+b[i]);}
int Find(double x)
{
	for(int i=root;;)
	{
		if(lk(i)<x)i=lc(i);
		else if(rk(i)>x)i=rc(i);
		else return i;
	}
}
double CalcK(double xx1,double yy1,double xx2,double yy2){return (xx1==xx2)?-oo:(yy1-yy2)/(xx1-xx2);}
int Merge(int x,int y)
{
	int i=x;
	for(;rc(i);i=rc(i));
	rc(i)=y;fa(y)=i;
	return x;
}
void Update()
{
	int t=root;
	if(!lc(t))
	{
		lk(t)=oo;
		rk(t)=lk(rc(t))=CalcK(x(t),y(t),x(rc(t)),y(rc(t)));
	}
	if(!rc(t))
	{
		rk(t)=-oo;
		lk(t)=rk(lc(t))=CalcK(x(t),y(t),x(lc(t)),y(lc(t)));
	}
	if(lc(t)&&rc(t))
	{
		lk(t)=rk(lc(t))=CalcK(x(t),y(t),x(lc(t)),y(lc(t)));
		rk(t)=lk(rc(t))=CalcK(x(t),y(t),x(rc(t)),y(rc(t)));
		if(lk(t)<=rk(t))
		{
			root=Merge(lc(t),rc(t));fa(root)=0;
			rk(root)=lk(rc(root))=CalcK(x(root),y(root),x(rc(root)),y(rc(root)));

		}
	}
}
int FixL()
{
	int s;
	for(int i=lc(root);i;)
	{
		if(CalcK(x(i),y(i),x(root),y(root))<lk(i))s=i,i=rc(i);
		else i=lc(i);
	}
	return s;
}
int FixR()
{
	int s;
	for(int i=rc(root);i;)
	{
		if(CalcK(x(i),y(i),x(root),y(root))>rk(i))s=i,i=lc(i);
		else i=rc(i);
	}
	return s;
}
void Insert(int t)
{
	y(t)=CalcY(t);x(t)=y(t)*r[t];int flag,i;
	for(i=root;i;)
	{
		if(x(i)>x(t)){flag=i;i=lc(i);}
		else if(x(i)<x(t)){flag=i;i=rc(i);}
		else if(y(i)>=y(t))return;
		else{y(i)=y(t),t=i;break;}
	}
	if(!i)if((x(flag)<x(t)))rc(flag)=t;else lc(flag)=t;
	if(!i)fa(t)=flag;
	Splay(t,root);
	if(lc(t))
	{
		flag=FixL();
		Splay(flag,lc(root));
		rc(flag)=0;
	}
	if(rc(t))
	{
		flag=FixR();
		Splay(flag,rc(root));
		lc(flag)=0;
	}
	Update();
}
void Init()
{
	base[0]=1;
	rep(i,1,18)base[i]=base[i-1]*10;
	fread(ipos=Input,10000000,1,stdin);
	n=read();s=getreal();
	scanf("%d%lf",&n,&s);
	rep(i,1,n){a[i]=getreal();b[i]=getreal();r[i]=getreal();}
}
void Work()
{
	f[1]=s;y(1)=CalcY(1);x(1)=y(1)*r[1];root=1;lk(1)=oo;rk(1)=-oo;
	rep(i,2,n)
	{
		int j=Find(-a[i]/b[i]);
		f[i]=max(f[i-1],x(j)*a[i]+y(j)*b[i]);
		Insert(i);
	}
	printf("%.3lf
",f[n]);
}
int main()
{
//	freopen((name+in).c_str(),"r",stdin);
//	freopen((name+out).c_str(),"w",stdout);
	Init();
	Work();
	return 0;
}