题意
农场主养了 $M$ 只猫，它们会到 $N$ 座山上去玩，在 $T_i$ 的时候下山。农场主雇了 $P$ 个员工，员工可以在不同的时刻从第 $1$ 座山出发去接猫。求所有猫等待时间和的最小值。
$N,M\le 10^5 \ , \ P\le 100$ 。
题解
用 $t_i$ 表示接第 $i$ 只猫的最早出发时间，显然 $t_i = T_i - D_{H_i}$ ，然后将所有猫按照 $t_i$ 排序。
用 $f[i][j]$ 表示当前第 $i$ 个员工接走前 $j$ 只猫的最少等待时间。枚举上一次接走的猫 $k$ ，那么当前需要接走 $[k+1,j]$ 的猫。
显然刚好接走第 $j$ 只猫是最优的情况，方程式为：
$$f[i][j] = \min_{k=0}^{j-1} ( f[i-1][k] + \sum_{p=k+1}^j (t_i-t_p))$$
令 $S_i = \sum_{j=1}^i t_j$：
$$f[i][j] = \min_{k=0}^{j-1} ( f[i-1][k] + (j-k)\times t_j - S_j + S_k)$$
出现乘积，考虑斜率优化，将与 $k$ 有关的式子挪到左边：
$$S_k + f[i-1][k] = t_j\times k + (f[i][j] + S_j + j\times t_j)$$
斜率 $t_j$ 显然单调。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
ll n,m,p,d[100005],t[100005],s[100005],q[100005],f[105][100005];
signed main()
{
n=read(); m=read(); p=read();
for (ll i=2;i<=n;i++) d[i]=d[i-1]+read();
for (ll i=1;i<=m;i++)
{
ll dis=d[read()];
t[i]=read()-dis;
}
sort(t+1,t+m+1);
for (ll i=1;i<=m;i++) s[i]=s[i-1]+t[i];
for (ll i=1;i<=m;i++) f[1][i]=i*t[i]-s[i];
ll ans=f[1][m];
for (ll i=2;i<=p;i++)
{
ll l=1,r=1; q[l]=0;
for (ll j=1;j<=m;j++)
{
while (l<r && s[q[l+1]]+f[i-1][q[l+1]]-s[q[l]]-f[i-1][q[l]]
<=(q[l+1]-q[l])*t[j]) l++;
f[i][j]=f[i-1][q[l]]+(j-q[l])*t[j]-s[j]+s[q[l]];
while (l<r && (s[q[r]]+f[i-1][q[r]]-s[q[r-1]]-f[i-1][q[r-1]])*(j-q[r])
>=(s[j]+f[i-1][j]-s[q[r]]-f[i-1][q[r]])*(q[r]-q[r-1])) r--;
q[++r]=j;
}
ans=min(ans,f[i][m]);
}
return !printf("%lld",ans);
}