DP/CDQ分治
orz Hzwer
copy了下他的代码……结果在while(j<top......)这一句中把一个括号的位置打错了……找了我一个多小时才找到TAT
很神奇……顺便贴下CDQ的论文吧
/**************************************************************
Problem: 1492
User: Tunix
Language: C++
Result: Accepted
Time:1420 ms
Memory:13388 kb
****************************************************************/ //BZOJ 1492
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>;
const double eps=1e-;
typedef long long LL;
/******************tamplate*********************/
int n,top,st[N];
double f[N];
struct Point{
double x,y,a,b,k,rate;
int w,id;
void out(){
printf("%lf %lf %lf %lf %lf %lf\n",x,y,a,b,k,rate);
}
}p[N],t[N];
double getk(int a,int b){
if (!b)return -1e20;
if (fabs(p[a].x-p[b].x)<eps)return 1e20;
return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
inline bool operator < (Point a,Point b){return a.k>b.k;}
void solve(int l,int r){
if (l==r){
f[l]=max(f[l],f[l-]);
p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);
p[l].x=p[l].rate*p[l].y;
return;
}
int l1,l2,mid=(l+r)>>,j=;
l1=l; l2=mid+;
F(i,l,r)
if (p[i].id<=mid) t[l1++]=p[i];
else t[l2++]=p[i];
F(i,l,r) p[i]=t[i]; solve(l,mid);
top=;
F(i,l,mid){
while(top>&&getk(st[top-],st[top])<getk(st[top-],i)+eps)
top--;
st[++top]=i;
}
st[++top]=;
F(i,mid+,r){
while(j<top && getk(st[j],st[j+])+eps>p[i].k)j++;
f[p[i].id]=max(f[p[i].id],
p[st[j]].x*p[i].a+p[st[j]].y*p[i].b);
}
solve(mid+,r);
l1=l;l2=mid+;
F(i,l,r)
if(((p[l1].x<p[l2].x||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y))||l2>r)&&l1<=mid)t[i]=p[l1++];
else t[i]=p[l2++];
F(i,l,r) p[i]=t[i];
} int main(){
#ifndef ONLINE_JUDGE
freopen("1492.in","r",stdin);
freopen("1492.out","w",stdout);
#endif
scanf("%d%lf",&n,&f[]);
F(i,,n){
scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
p[i].k=-p[i].a/p[i].b; p[i].id=i;
}
sort(p+,p+n+);
solve(,n);
printf("%.3lf",f[n]);
return ;
}