BZOJ_3963_[WF2011]MachineWorks_斜率优化+CDQ分治

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef double f2;
#define N 200050
#define eps 1e-6
#define mem(x) memset(x,0,sizeof(x))
ll f[N],D[N],P[N],R[N],G[N],C;
int n,Case,S[N],t[N],tmp[N];
#define Y(j) (f[j]-P[j]-D[j]*G[j]-G[j]+R[j])
#define X(j) (G[j])
#define K(i) (-D[i])
struct A {
    ll d,p,r,g;
    bool operator < (const A &x) const {
        return d<x.d;
    }
}a[N];
f2 getK(int p1,int p2) {
    if(fabs(X(p2)-X(p1))<eps) return Y(p2)>Y(p1)?1e15:-1e15;
    return (1.0*Y(p2)-Y(p1))/(X(p2)-X(p1));
}
void solve(int l,int r) {
    if(l==r) return ;
    int mid=(l+r)>>1;
    solve(l,mid);
    int i,j,k;
    int top=0;
    for(i=l;i<=mid;i++) {
        if(f[t[i]]<P[t[i]]) continue;
        while(top>1&&getK(S[top-1],S[top])<=getK(S[top-1],t[i])) top--;
        S[++top]=t[i];
    }
    for(j=1,i=mid+1;i<=r;i++) {
        while(j<top&&getK(S[j],S[j+1])+eps>=K(t[i])) j++;
        f[t[i]]=max(f[t[i]],Y(S[j])-K(t[i])*X(S[j]));
    }
    solve(mid+1,r);
    i=l,j=l,k=mid+1;
    while(j<=mid&&k<=r) {
        if(X(t[j])<X(t[k])) tmp[i++]=t[j++];
        else tmp[i++]=t[k++];
    }
    while(j<=mid) tmp[i++]=t[j++]; 
    while(k<=r) tmp[i++]=t[k++];
    for(i=l;i<=r;i++) t[i]=tmp[i];
}
int work() {
    Case++;
    ll tmp;
    scanf("%d%lld%lld",&n,&C,&tmp); D[n+1]=tmp+1;
    if(n==0) return 0;
    int i,j;
    for(i=1;i<=n;i++) {
        scanf("%lld%lld%lld%lld",&a[i].d,&a[i].p,&a[i].r,&a[i].g);
    }
    /*if(Case!=17) return 1;
    printf("%d %lld %lld\n",n,C,tmp);
    for(i=1;i<=n;i++) printf("%lld %lld %lld %lld\n",a[i].d,a[i].p,a[i].r,a[i].g);
    return 0;*/
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++) D[i]=a[i].d,P[i]=a[i].p,R[i]=a[i].r,G[i]=a[i].g,t[i]=i;
    // for(i=1;i<=n;i++) printf("%lld\n",D[i]);
    n++; f[0]=C; t[n]=n;
    for(i=1;i<=n;i++) f[i]=-K(i)*X(0)+Y(0);
    solve(1,n);
    /*for(i=1;i<=n;i++) {
        for(j=1;j<i;j++) {
            if(f[j]>=P[j])
            f[i]=max(f[i],-K(i)*X(j)+Y(j));
        }
        printf("%lld\n",f[i]);
    }*/
    printf("Case %d: %lld\n",Case,f[n]);
    return 1;
}
int main() {
    while(1) {
        mem(a); mem(D); mem(P); mem(R); mem(f); mem(G); mem(t); mem(tmp); mem(S);
        int tmp=work();
        if(!tmp) return 0;
    }
}