bzoj4700

题解：

cdq分治

先考虑没有人被秒掉的情况

代码：

#include<bits/stdc++.h>

#define y1 ____y1

const int N=;

using namespace std;

typedef long long ll;

int bh[N],q[N],bhd[N],bha[N],A[N],d[N],P[N],T[N],n,atk;

ll ans,pr,K[N];

int comp1(const int x,const int y)

{

    return A[x]*d[y]>A[y]*d[x];

}

int fc(int x,int y,int z)

{

    ll x1=d[x],y1=K[x],x2=d[y],y2=K[y],x3=d[z],y3=K[z];

    return (y1-y2)*(x2-x3)>=(y2-y3)*(x1-x2);

}

void cdq(int xl,int xr)

{

    if (xl==xr)return;

    int mid=xl+xr>>;

    cdq(xl,mid);cdq(mid+,xr);

    int l=,r=;

    for (int i=xl;i<=mid;i++)

     {

        while (l<r&&fc(bhd[i],q[r],q[r-]))r--;

        q[++r]=bhd[i];

     }

    for (int i=mid+;i<=xr;i++)

     {

        while (l<r&&K[q[l]]-K[q[l+]]<=(ll)A[bha[i]]*(d[q[l]]-d[q[l+]]))l++;

        if (l<=r)ans=max(ans,K[bha[i]]+K[q[l]]-(ll)A[bha[i]]*d[q[l]]);

     }

    int i=xl,j=mid+,ptr=xl;

    for (;i<=mid&&j<=xr;)

     {

        if (d[bhd[i]]<d[bhd[j]])bh[ptr++]=bhd[i++];

        else bh[ptr++]=bhd[j++];

     }

    for (;i<=mid;)bh[ptr++]=bhd[i++];

    for (;j<=xr;)bh[ptr++]=bhd[j++];

    for (int i=xl;i<=xr;i++)bhd[i]=bh[i];

    i=xl,j=mid+,ptr=xl;

    for (;i<=mid&&j<=xr;)

     {

        if (d[bha[i]]<d[bha[j]])bh[ptr++]=bha[i++];

        else bh[ptr++]=bha[j++];

     }

    for (;i<=mid;)bh[ptr++]=bha[i++];

    for (;j<=xr;)bh[ptr++]=bha[j++];

    for (int i=xl;i<=xr;i++)bha[i]=bh[i];

}

int main()

{

    scanf("%d%d",&n,&atk);

    for (int i=;i<=n;i++)bh[i]=i;

    for (int i=;i<=n;i++)

     {

        scanf("%d%d",&A[i],&d[i]);

        d[i]=(d[i]-)/atk+;

     }

    sort(bh+,bh+n+,comp1);

    for (int i=;i<=n;i++)

     {

        P[i]=P[i-]+d[bh[i]];

        T[i]=T[i-]+A[bh[i]];

        bhd[i]=bha[i]=bh[i];

     }

    for (int i=;i<=n;i++)

     {

        K[bh[i]]=(ll)A[bh[i]]*(P[i]-)+(ll)(T[n]-T[i])*d[bh[i]];

        pr+=(ll)A[bh[i]]*(P[i]-);

     }

    cdq(,n);

    printf("%lld",pr-ans);

    return ;

}