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

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 10000
#define inf 0x7fffffff
struct haha{
	int next,to,w,cost,from;
}edge[N];
int cnt=2,head[N];
int t,g,p,m,f,n,s;
void add(int u,int v,int w,int c){
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].cost=c;
	edge[cnt].from=u;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
int S,T;
queue<int> q;
int dis[N],cun[N],flag[N],from[N],ans;
int spfa(int st,int ed)
{
	  pos(i,st+1,ed){
	  	dis[i]=inf;
	  }
	  flag[st]=1;
	  q.push(st); 
	  while(!q.empty())
	  {
	    int k=q.front();
	    q.pop();
	    flag[k]=0;
	    for(int i=head[k];i;i=edge[i].next)
	    {
	      if(edge[i].w&&dis[edge[i].to]>dis[k]+edge[i].cost)
	      {
	        dis[edge[i].to]=dis[k]+edge[i].cost;
	        if(!flag[edge[i].to])
			  q.push(edge[i].to);
	        flag[edge[i].to]=1;
			from[edge[i].to]=i;
	      }
	    }
	  }
	  if(dis[ed]==inf)
	    return 0;
	  return dis[ed];
}
int work(int st,int ed)
{
	  int pp=ed,ff=inf;
	  while(pp!=st)
	  {
	    ff=min(ff,edge[from[pp]].w);
	    pp=edge[from[pp]^1].to;
	  }
	  pp=ed;
	  while(pp!=st)
	  {
	    edge[from[pp]].w-=ff;
	    edge[from[pp]^1].w+=ff;
	    pp=edge[from[pp]^1].to;
	  }
	  return ff;
}
int MCMF(int st,int ed)
{
	  int ret=0,l;
	  while(l=spfa(st,ed))
	    ret+=work(st,ed)*l;
	  return ret;
}
void work(){
	pos(i,1,t){
		add(S,i,cun[i],0);
		add(i,S,0,0);
		
		add(S,i+t,inf,p);
		add(i+t,S,0,-p);
		
		add(i+t,T,cun[i],0);
		add(T,i+t,0,0);
		
		if(i+m<=t){
			add(i,i+m+t,inf,f);
			add(i+m+t,i,0,-f);
		}
		if(i+n<=t){
			add(i,i+n+t,inf,s);
			add(i+n+t,i,0,-s);
		}
		if(i!=t){
			add(i,i+1,inf,0);
			add(i+1,i,0,0);
		}
	}
}
int main(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d",&t);
	T=t*2+1;
	pos(i,1,t){
		scanf("%d",&cun[i]);
	}
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	work();
	ans=MCMF(S,T);
	cout<<ans;
	return 0;
}