按卖出时间排序后，设f[i]为买下第i台机器后的当前最大收益，则显然有f[i]=max{f[j]+g_j*(d_i-d_j-1)+r_j-p_i}，且若此值<0，应设为-inf以表示无法购买第i台机器。

　　考虑优化，显然是一个斜率优化式子，设j转移优于k，则f[j]+g_j(d_i-d_j-1)+r_j>f[k]+g_k(d_i-d_k-1)+r_k，移项得(f[j]-g_jd_j-g_j+r_j)-(f[k]-g_kd_k-g_k+r_k)>d_i(g_k-g_j)。g没有单调性，于是cdq分治，按g排序建上凸壳即可。

　　注意比较斜率时只能用long double，因为乘法会溢出。对于横坐标相同的点需要特判一下，如果加进去的点纵坐标较大就把之前的点弹掉。感觉每次写斜率优化对这种问题都毫无办法。复杂度O(nlogn)。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 100010#define inf 2000000000000000000llchar getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int T,n,m,k,q[N];struct data{ int d,p,r,g,i;ll ans; bool operator <(const data&a) const { return d
           
            =calc(y); return (long double)(calc(i)-calc(y))/(a[i].g-a[y].g)>=(long double)(calc(y)-calc(x))/(a[y].g-a[x].g);}void solve(int l,int r){ if (l>=r) return; int mid=l+r>>1; solve(l,mid); int head=1,tail=0; for (int i=l;i<=mid;i++) { while (tail>1&&check(q[tail-1],q[tail],i)) tail--; q[++tail]=i; } for (int i=mid+1;i<=r;i++) { while (head
            
             -1ll*a[i].d*(a[q[head+1]].g-a[q[head]].g)) head++; if (calc(q[head])+1ll*a[q[head]].g*a[i].d-a[i].p>=0) a[i].ans=max(a[i].ans,calc(q[head])+1ll*a[q[head]].g*a[i].d-a[i].p); } solve(mid+1,r); int i=l,j=mid+1; for (int k=l;k<=r;k++) if (i<=mid&&a[i].g
             
              r) b[k]=a[i++]; else b[k]=a[j++]; for (int k=l;k<=r;k++) a[k]=b[k];}int main(){#ifndef ONLINE_JUDGE freopen("bzoj3963.in","r",stdin); freopen("bzoj3963.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(),k=read(); while (n) { for (int i=1;i<=n;i++) a[i].d=read(),a[i].p=read(),a[i].r=read(),a[i].g=read(),a[i].i=i; n++,a[n].d=k+1,a[n].p=a[n].r=a[n].g=0; sort(a+1,a+n+1); for (int i=1;i<=n;i++) a[i].ans=-inf;a[0].ans=m; solve(0,n); for (int i=1;i<=n;i++) a[0].ans=max(a[0].ans,a[i].ans); printf("Case ");printf("%d",++T);printf(": ");printf(LL,a[0].ans); n=read(),m=read(),k=read(); } return 0;}