暴力解决法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m,p;
int d[N],h[N],t[N],Q[N];
ll f[N],g[N],a[N],S[N];
double slope(int x,int y)  {return 1.0*((g[x]+S[x])-(g[y]+S[y]))/(x-y);}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=2;i<=n;++i)  scanf("%d",&d[i]),d[i]+=d[i-1];
	for(int i=1;i<=m;++i)  scanf("%d%d",&h[i],&t[i]),a[i]=t[i]-d[h[i]];
	sort(a+1,a+m+1);
	for(int i=1;i<=m;++i)  S[i]=S[i-1]+a[i];
	memset(f,0x3f,sizeof(f)),f[0]=0;
	for(int j=1;j<=p;++j){
		int l=0,r=0;
		memcpy(g,f,sizeof(g));
		for(int i=1;i<=m;++i){
			while(l<r&&slope(Q[l],Q[l+1])<=a[i])  ++l;
			f[i]=g[Q[l]]+a[i]*(i-Q[l])-(S[i]-S[Q[l]]);
			while(l<r&&slope(Q[r-1],Q[r])>=slope(Q[r],i))  --r;
			Q[++r]=i;
		}
	}
	printf("%lld\n",f[m]);
	return 0;
}