记录编号	431176	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-07-31 11:46:14	内存使用	0.10 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct edge{
	int e,n,flow,cost;
}a[20010];
int pre[410],tot;
inline void insert(int s,int e,int flow,int cost){
	a[tot].e=e;
	a[tot].flow=flow;
	a[tot].cost=cost;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int S(0),T;
int N,p,m,f,n,s;
int r[201];
int flow(0),ans(0),inf(0x7fffffff);
inline void build(){
	for(int i=1;i<=N;i++){
		insert(S,i,r[i],0),insert(i,S,0,0);
		insert(S,i+N,inf,p),insert(i+N,S,0,-p);
		insert(i+N,T,r[i],0),insert(T,i+N,0,0);
		if(i+m<=N)
			insert(i,i+m+N,inf,f),insert(i+m+N,i,0,-f);
		if(i+n<=N)
			insert(i,i+n+N,inf,s),insert(i+n+N,i,0,-s);
		if(i!=N)
			insert(i,i+1,inf,0),insert(i+1,i,0,0);
	}
}
int dis[410],fa[410],path[410];
bool vis[410];
inline bool bfs(){
	memset(vis,0,sizeof(vis));
	memset(dis,30,sizeof(dis));
	memset(fa,-1,sizeof(fa));
	queue<int>q;
	q.push(S);
	dis[S]=0;
	vis[S]=1;
	while(!q.empty()){
		int k(q.front());
		vis[k]=0;
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(a[i].flow&&dis[e]>dis[k]+a[i].cost){
				dis[e]=dis[k]+a[i].cost;
				fa[e]=k;
				path[e]=i;
				if(!vis[e])
					q.push(e),vis[e]=1;
			}
		}
	}
	if(fa[T]==-1)
		return false;
	return true;
}
inline void dinic(){
	while(bfs()){
		int f(inf);
		for(int i=T;i!=S;i=fa[i])
			if(a[path[i]].flow<f)
				f=a[path[i]].flow;
		flow+=f;
		ans+=dis[T]*f;
		for(int i=T;i!=S;i=fa[i]){
			a[path[i]].flow-=f;
			a[path[i]^1].flow+=f;
		}
	}
}
inline int gg(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	scanf("%d",&N);
	T=(N<<1)+1;
	for(int i=1;i<=N;i++)
		scanf("%d",&r[i]);
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	build();
	dinic();
	printf("%d",ans);
	return 0;
}
int K(gg());
int main(){;}