记录编号	382558	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2010] 基站选址	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.671 s
提交时间	2017-03-14 08:03:21	内存使用	9.83 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20010,maxk=110;
struct A{
	int l,r,w;
	bool operator<(const A &a)const{return r<a.r;}
}a[maxn];
void build(int,int,int);
void modify(int,int,int,int,int,int);
int query(int,int,int,int,int);
int mn[maxn<<2],lazy[maxn<<2];
int d[maxn],c[maxn],s[maxn],w[maxn];
int n,m,k,f[maxn][maxk],ans=0;
int main(){
	freopen("base.in","r",stdin);
	freopen("base.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)scanf("%d",&d[i]);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)scanf("%d",&s[i]);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].w);
		a[i].l=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
		a[i].r=upper_bound(d+1,d+n+1,d[i]+s[i])-d-1;
		f[a[i].r+1][1]+=a[i].w;
		w[a[i].l-1]+=a[i].w;
		ans+=a[i].w;//printf("l=%d r=%d w=%d\n",a[i].l,a[i].r,a[i].w);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)f[i][1]+=f[i-1][1];
	for(int i=n;i;i--)w[i]+=w[i+1];
	for(int i=1;i<=n;i++){
		f[i][1]+=c[i];
		ans=min(ans,f[i][1]+w[i]);
	}
	//for(int i=1;i<=n;i++)printf("f[%d][0]=%d w=%d\n",i,f[i][0],w[i]);
	f[1][1]=c[1];
	for(k=2;k<=m;k++){
		int cur=1;
		build(1,n,1);
		for(int i=k;i<=n;i++){
			while(cur<=n&&a[cur].r<i){
				if(a[cur].l>=k)modify(k-1,a[cur].l-1,a[cur].w,1,n,1);//printf("%d~%d += %d\n",1,a[cur].l-1,a[cur].w);
				cur++;
			}
			f[i][k]=query(k-1,i-1,1,n,1)+c[i];//printf("f[%d][%d]=%d c[i]=%d\n",i,k,f[i][k],c[i]);
			ans=min(ans,f[i][k]+w[i]);
		}
	}
	printf("%d",ans);
	return 0;
}
void build(int l,int r,int rt){
	lazy[rt]=0;
	if(l==r){
		mn[rt]=f[l][k-1];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void modify(int s,int t,int d,int l,int r,int rt){
	if(s<=l&&t>=r){
		mn[rt]+=d;
		lazy[rt]+=d;
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)modify(s,t,d,l,mid,rt<<1);
	if(t>mid)modify(s,t,d,mid+1,r,rt<<1|1);
	mn[rt]=min(mn[rt<<1],mn[rt<<1|1])+lazy[rt];
}
int query(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return mn[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return query(s,t,l,mid,rt<<1)+lazy[rt];
	if(s>mid)return query(s,t,mid+1,r,rt<<1|1)+lazy[rt];
	return min(query(s,t,l,mid,rt<<1),query(s,t,mid+1,r,rt<<1|1))+lazy[rt];
}
/*
5 2
1 7 13 17
5 3 6 4 1
7 9 8 0 2
9 5 6 4 3
*/