题解：
首先我们观察到山与距离其实是没有什么用的，因为对于任意一只猫，我们都可以直接算出如果有一个人要恰好接走它，需要在哪一时刻出发，我们设第i只猫对应的这个时刻为$t_{i}$.
注意这个$t_{i}$是我自己新定义的，跟题目中的没有关系，下面所写的t都是我现在所定义的t，而跟原题面中的t没有任何关系。
然后我们对t数组排个序，于是题意转化为了有m只猫，每只猫有一个权值$t_{i}$,如果出发时间大于等于$t_{i}$,则可以接到第i只猫。设出发时间为x，则接到第i只猫时，这只猫会等待$x - t_{i}$的时间。现在有p个人，要求为每个人指定一个时间使得所有猫的等待时间之和最小。
然后我们继续转化题意。
观察到每个人相当于会选择一只猫i，然后选择在$t_{i}$时刻出发，恰好接走这只猫，顺便可以接走其他可以被接走的猫。
为什么是每个人都必须选一只猫呢？
观察到如果一个人出发，没有任何一只猫是恰好被接到的，所有猫都是等了一会再被接走的，那么这个人为什么不早出发一点，恰好接走一些猫呢？这样不仅可以接走和上一种方案相同的猫，还可以减小等待时间。
于是现在题意转化为了有m只猫，每只猫有一个权值$t_{i}$。如果第x个人选择了第i只猫，上一个出发的人选了第j只猫，则这个人可以接走[j + 1, i]中的所有猫，并且代价为$sum_{k = j + 1}^{i}{t_{i} - t_{k}}$。现在有p个人，要求为每个人指定一只猫使得所有猫的等待时间之和最小。
先化一下式子：(其中s[i]表示$sum_{k = 1}^{i}{t[k]}$)
$$sum_{k = j + 1}^{i}{t_{i} - t_{k}}$$
$$= sum_{k = j + 1}^{i}{t_{i}} - sum_{k = j + 1}^{i}{t_{k}}$$
$$= (i - j) t_{i} - (s[i] - s[j])$$
于是我们设f[i][j]表示DP到第i个人，这个人选择了第j只猫的最小代价。
然后暴力枚举i，j，转移的时候再暴力枚举前一个人选了哪只猫即可。
但是这样的复杂度是$pm^2$的，观察到我们优化到$pm$就可以过了，又注意到式子中有一个跟i相关的量和一个跟j相关的量的乘积，我们考虑一下斜率优化。
我们先化一波式子。
$$f[i][j] = f[i - 1][k] + (j - k) t_{j} - (s[j] - s[k])$$
$$Rightarrow f[i][j] = f[i - 1][k] + jt_{j} - kt_{j} - s[j] + s[k]$$
$$Rightarrow -s[k] - f[i - 1][k] = -kt_{j} + jt_{j} - s[j] - f[i][j]$$
$$Rightarrow s[k] + f[i - 1][k] = t_{j}k - jt_{j} + s[j] + f[i][j]$$
代入y = kx + b可以得到$y = s[k] + f[i - 1][k], x = k, K = t_{j}, b = -jt_{j} + s[j] + f[i][j]$。
斜优式子已经出来了，现在就是要证明单调性了。
首先$K = t_{j}$本来就是排好序的，所以从小到大枚举j，所以每次加入的决策点$(x, y)$中的$x = j$肯定是递增的，$t_{j}$肯定也是递增的。
所以就可以直接上斜优了。
然而写的时候发现我对计算几何一无所知，，，凸包维护错了调了好久QAQ
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 110 5 #define ac 120000 6 #define LL long long 7 8 int n, m, p, Head, tail, now; 9 LL ans; 10 LL f[AC][ac], d[ac], t[ac], sum[ac], s[ac]; 11 12 inline int read() 13 { 14 int x = 0;char c = getchar(); 15 while(c > '9' || c < '0') c = getchar(); 16 while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 17 return x; 18 } 19 20 inline void pre() 21 { 22 n = read(), m = read(), p = read(); 23 for(R i = 2; i <= n; i ++) d[i] = read() + d[i - 1];//顺便统计一下前缀和 24 for(R i = 1; i <= m; i ++) 25 { 26 LL tmp = read(); 27 t[i] = read() - d[tmp]; 28 } 29 sort(t + 1, t + m + 1); 30 for(R i = 1; i <= m; i ++) sum[i] = sum[i - 1] + t[i];//这个要放在排好序之后 31 } 32 33 inline void upmin(LL &a, LL b){ 34 if(b < a) a = b; 35 } 36 37 inline LL Y(int k){ 38 return sum[k] + f[now][k]; 39 } 40 41 inline LL cross(int a, int b, int c){//算叉积 42 LL x1 = a - b, x2 = b - c, y1 = Y(a) - Y(b), y2 = Y(b) - Y(c); 43 return x1 * y2 - x2 * y1; 44 } 45 46 inline LL cal(int x, int k){//算出y - kx,表示b的大小 47 return Y(x) - t[k] * x; 48 } 49 50 inline void work() 51 { 52 for(R i = 1; i <= m; i ++) 53 f[1][i] = i * t[i] - sum[i];//先算出第一个人的 54 ans = f[1][m]; 55 for(R i = 2; i <= p; i ++)//枚举人 56 { 57 Head = 1, tail = 0, now = i - 1; 58 s[++tail] = 0;//0也是一个决策点 59 for(R j = 1; j <= m; j ++)//枚举当前选择的猫 60 { 61 while(Head < tail && cal(s[Head + 1], j) < cal(s[Head], j)) ++ Head; 62 int x = s[Head]; 63 f[i][j] = f[i - 1][x] + (j - x) * t[j] - sum[j] + sum[x]; 64 while(Head < tail && cross(j, s[tail], s[tail - 1]) > 0) -- tail; 65 s[++ tail] = j; 66 } 67 upmin(ans, f[i][m]); 68 } 69 printf("%lld ", ans); 70 } 71 72 int main() 73 { 74 freopen("in.in", "r", stdin); 75 pre(); 76 work(); 77 fclose(stdin); 78 return 0; 79 }