【BZOJ】【1492】【NOI207】货币兑换Cash DP/CDQ分治

 1 /**************************************************************
 2     Problem: 1492
 3     User: Tunix
 4     Language: C++
 5     Result: Accepted
 6     Time:1420 ms
 7     Memory:13388 kb
 8 ****************************************************************/
 9  
10 //BZOJ 1492
11 #include<cmath>
12 #include<cstdio>
13 #include<cstdlib>
14 #include<iostream>
15 #include<algorithm>
16 #define rep(i,n) for(int i=0;i<n;++i)
17 #define F(i,j,n) for(int i=j;i<=n;++i)
18 #define D(i,j,n) for(int i=j;i>=n;--i)
19 using namespace std;
20 inline int getint(){
21     int v=0,sign=1; char ch=getchar();
22     while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
23     while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
24     return v*sign;
25 }
26 const int N=1e5+10,INF=~0u>>2;
27 const double eps=1e-9;
28 typedef long long LL;
29 /******************tamplate*********************/
30 int n,top,st[N];
31 double f[N];
32 struct Point{
33     double x,y,a,b,k,rate;
34     int w,id;
35     void out(){
36         printf("%lf %lf %lf %lf %lf %lf
",x,y,a,b,k,rate);
37     }
38 }p[N],t[N];
39 double getk(int a,int b){
40     if (!b)return -1e20;
41     if (fabs(p[a].x-p[b].x)<eps)return 1e20;
42     return (p[b].y-p[a].y)/(p[b].x-p[a].x);
43 }
44 inline bool operator < (Point a,Point b){return a.k>b.k;}
45 void solve(int l,int r){
46     if (l==r){
47         f[l]=max(f[l],f[l-1]);
48         p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);
49         p[l].x=p[l].rate*p[l].y;
50         return;
51     }
52     int l1,l2,mid=(l+r)>>1,j=1;
53     l1=l; l2=mid+1;
54     F(i,l,r)
55         if (p[i].id<=mid) t[l1++]=p[i];
56         else t[l2++]=p[i];
57     F(i,l,r) p[i]=t[i];
58  
59  
60     solve(l,mid);
61     top=0;
62     F(i,l,mid){
63         while(top>1&&getk(st[top-1],st[top])<getk(st[top-1],i)+eps)
64             top--;
65         st[++top]=i;
66     }
67     st[++top]=0;
68     F(i,mid+1,r){
69         while(j<top && getk(st[j],st[j+1])+eps>p[i].k)j++;
70         f[p[i].id]=max(f[p[i].id],
71                 p[st[j]].x*p[i].a+p[st[j]].y*p[i].b);
72     }
73     solve(mid+1,r);
74     l1=l;l2=mid+1;
75     F(i,l,r)
76         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++];
77         else t[i]=p[l2++];
78     F(i,l,r) p[i]=t[i];
79 }
80  
81 int main(){
82 #ifndef ONLINE_JUDGE
83     freopen("1492.in","r",stdin);
84     freopen("1492.out","w",stdout);
85 #endif
86     scanf("%d%lf",&n,&f[0]);
87     F(i,1,n){
88         scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
89         p[i].k=-p[i].a/p[i].b; p[i].id=i;
90     }
91     sort(p+1,p+n+1);
92     solve(1,n);
93     printf("%.3lf",f[n]);
94     return 0;
95 }