记录编号	410767	评测结果	AAAAAAAAAA
题目名称	准备工作	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.765 s
提交时间	2017-06-02 14:23:14	内存使用	5.65 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
struct edge{int f,t,g;}w[N];
int head[N],next[N],cnt;
void add(int f,int t,int g){
	w[++cnt]=(edge){f,t,g};
	next[cnt]=head[f];
	head[f]=cnt;
	w[++cnt]=(edge){t,f,0};
	next[cnt]=head[t];
	head[t]=cnt;
}
struct st{
	int x,i,df;
	st(int X=0,int DF=0){x=X;i=head[x];df=DF;}
}z[N];
int top,l[N],s,t,ans;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;ans+=df;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[z[i].i^1].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=s;i<=t;i++) l[i]=0;
	l[s]=1;Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		if (l[t]) continue;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[t]) return 0;
	z[top=1]=st(s,1e9);
	while (top){
		if (V==t) change(),top--,E=next[E];else
		if (!E) l[V]=0,top--,E=next[E];else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=st(w[E].t,min(F,w[E].g)),top++;
		else E=next[E];
	}
	return 1;
}
int p[N],d[N];
int n,a[N],L[N],R[N];
//点i对应时间段(a[i],a[i+1])
void solve(int l,int r){
	if (l==r) return (void)printf("%d\n",l);
	int mid=(l+r)>>1;
	if (mid==r) mid--;
	for (int i=1;i<=n;i++) R[i]=mid+d[i];//最晚做到这个时候
	int m=0;a[++m]=0;
	for (int i=1;i<=n;i++) a[++m]=L[i],a[++m]=R[i];
	sort(a+1,a+m+1);
	s=0;t=n+m+1;
	//初始化
	for (int i=s;i<=t;i++) head[i]=0;
	cnt=1;ans=0;
	//时间段编号[1,m]，任务编号[m+1,m+n]
	for (int i=1;i<m;i++) add(i,t,a[i+1]-a[i]);
	for (int i=1;i<=n;i++){
		add(s,i+m,p[i]);//需要花费p[i]时间
		ans-=p[i];
		for (int j=1;j<m;j++)
			if (L[i]<=a[j]&&R[i]>=a[j+1]) add(i+m,j,1e9);
	}
	while (dinic());
	if (!ans) solve(l,mid);else solve(mid+1,r);
}
int main()
{
	freopen("preparation.in","r",stdin);
	freopen("preparation.out","w",stdout);
	while (1){
		scanf("%d",&n);
		if (!n) break;
		for (int i=1;i<=n;i++) scanf("%d",&p[i]);
		for (int i=1;i<=n;i++) scanf("%d",&L[i]);
		for (int i=1;i<=n;i++) scanf("%d",&d[i]);
		solve(-1e6,1e6);
	}
	return 0;
}