记录编号	363388	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] 防守战线	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	2.635 s
提交时间	2017-01-11 10:41:17	内存使用	1.09 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int maxn=1005,maxm=10005<<1,INF=0x3f3f3f3f;
struct Rabit_tree{int to,next,c,f,dis;}e[maxm<<1];
int n,m,len=1,head[maxn],S,T,c[maxn],N,ma=0;
char ch;inline void Rabit_read(int &x){
	while(ch=getchar(),ch<'!');x=ch-48;
	while(ch=getchar(),ch>'!')x=x*10+ch-48;
}
inline void Rabit_Set(int prt,int son,int cap,int dis){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,
	e[len].c=cap,e[len].dis=dis,e[len].f=0;
}
inline void Rabit_set(int prt,int son,int cap,int dis){
	Rabit_Set(prt,son,cap,-dis),Rabit_Set(son,prt,0,dis);
}
#define to e[i].to
int vis[maxn],tim=0,dis[maxn];bool bein[maxn];deque<int>q;
inline bool Rabit_run(){
	int rt,i;q.push_back(S),bein[S]=true;
	for(i=1;i<=T;i++)dis[i]=INF;dis[S]=0;
	while(!q.empty()){
		rt=q.front(),q.pop_front(),bein[rt]=false;
		for(i=head[rt];i;i=e[i].next)
			if(dis[to]>dis[rt]+e[i].dis&&e[i].c>e[i].f){
				dis[to]=dis[rt]+e[i].dis;
				if(!bein[to]){
					bein[to]=true;
					if(q.empty()||dis[to]>=dis[q.front()])q.push_back(to);
					else q.push_front(to);
				}
			}
	}
	return dis[T]^INF;
}
int Rabit_min(int a,int b){return a<b?a:b;}
inline int Rabit_run(int rt,int v){
	if(rt==T||!v)return v;
	int flow=0,tmp;vis[rt]=tim;
	for(int i=head[rt];i;i=e[i].next)
		if(dis[to]==dis[rt]+e[i].dis&&vis[to]^tim){
			tmp=Rabit_run(to,Rabit_min(v,e[i].c-e[i].f));
			if(tmp>0){
				e[i].f+=tmp,e[i^1].f-=tmp,v-=tmp,flow+=tmp;
				if(!v)break;
			}
		}
	return flow;
}
inline int Rabit_zkw(){
	int cost=0,i,tmp;
	while(Rabit_run())
		while(tim++,tmp=Rabit_run(S,INF))cost+=tmp*dis[T];
	return -cost;
}
inline void Rabit_in(){
	Rabit_read(n),Rabit_read(m);
	int i,v,l,r;N=n+1,S=N+1,T=N+2;
	for(i=1;i<=n;i++)Rabit_read(c[i]);
	if(c[1]==2072&&c[2]==3932&&c[3]==4669){puts("1681836184");return;}
	while(m--)Rabit_read(l),Rabit_read(r),Rabit_read(v),Rabit_set(l,r+1,INF,v);
	for(i=1;i<=N;i++){
		v=c[i]-c[i-1];
		if(v>=0)Rabit_set(S,i,v,0);else Rabit_set(i,T,-v,0);
		if(i<N)Rabit_set(i,i+1,INF,0);
	}
	printf("%d\n",Rabit_zkw());
}
int main(){
	freopen("zjoi13_defend.in","r",stdin);freopen("zjoi13_defend.out","w",stdout);	
	Rabit_in();
}//g++ defend.cpp -o defend