文件详细信息

下载本文件

本文件的大小为 1008 字节。

// LUOGU_RID: 100365082
#include<algorithm>
#include<cstdio>
#include<cstring>
typedef long long ll;
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num; 
}
void write(ll a){
	if(a>=10)write(a/10);
	putchar(a%10|48);
}
const int maxn=100005,maxm=100005;
int n,m,p;
int d[maxn],a[maxm];
ll s[maxm],g[maxm],f[maxm];
int l,r,q[maxm];
int main(){
	n=read(),m=read(),p=read();
	for(int i=2;i<=n;i++)d[i]=d[i-1]+read();
	int h,t;
	for(int i=1;i<=m;i++){
		h=read(),t=read();
		a[i]=t-d[h];
	}
	std::sort(a+1,a+m+1);
	for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
	memset(f,0x3f,sizeof(ll[m+5]));
	f[0]=g[0]=0;
	for(int i=1;i<=p;i++){
		q[l=r=1]=0;
		for(int j=1;j<=m;j++){
			g[j]=f[j]+s[j];
			while(l<r&&(g[j]-g[q[r]])*(q[r]-q[r-1])<(g[q[r]]-g[q[r-1]])*(j-q[r]))r--;
			q[++r]=j;
			while(l<r&&(ll)a[j]*(q[l+1]-q[l])>g[q[l+1]]-g[q[l]])l++;
			int k=q[l];
			f[j]=g[k]+(ll)a[j]*(j-k)-s[j];
		}
	}
	write(f[m]);
	return 0;
}