AcWing 301. 任务安排2
原题链接
困难
作者:
wangyj
,
2021-01-23 10:21:29
,
所有人可见
,
阅读 522
#include<cstring>
#include<iostream>
using namespace std;
int n,m,a[300005],i,j,h=0,t=0;
long long c[300005],b[300005],f[300005];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld%lld",&b[i],&c[i]);
b[i]+=b[i-1],c[i]+=c[i-1];
}
a[0]=0;
for(i=1;i<=n;i++){
while(h<t&&(f[a[h+1]]-f[a[h]])<=(b[i]+m)*(c[a[h+1]]-c[a[h]]))h++;
j=a[h],f[i]=f[j]-(b[i]+m)*c[j]+b[i]*c[i]+m*c[n];
while(h<t&&(int)(f[a[t]]-f[a[t-1]])*(c[i]-c[a[t-1]])>=(int)(f[i]-f[a[t-1]])*(c[a[t]]-c[a[t-1]]))t--;
a[++t]=i;
}
printf("%lld\n", f[n]);
return 0;
}