AcWing 302. 任务安排3
原题链接
困难
作者:
wangyj
,
2021-01-24 10:11:36
,
所有人可见
,
阅读 596
#include<iostream>
using namespace std;
int n,s,b[300005],i,j,h=0,t=0,l,r,mid;
long long a[300005],c[300005],f[300005];
int main()
{
scanf("%d%d",&n,&s);
for(i=1;i<=n;i++)scanf("%lld%lld",&a[i],&c[i]),a[i]+=a[i-1],c[i]+=c[i-1];
b[0]=0;
for(i=1;i<=n;i++){
l=h,r=t;
while(l<r){
mid=l+r>>1;
if(f[b[mid+1]]-f[b[mid]]>(a[i]+s)*(c[b[mid+1]]-c[b[mid]]))r=mid;
else l=mid+1;
}
j=b[r],f[i]=f[j]-(a[i]+s)*c[j]+a[i]*c[i]+s*c[n];
while(h<t&&(double)(f[b[t]]-f[b[t-1]])*(c[i]-c[b[t-1]])>=(double)(f[i]-f[b[t-1]])*(c[b[t]]-c[b[t-1]]))t--;
b[++t]=i;
}
printf("%lld\n",f[n]);
return 0;
}