记录编号	240290	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	2.953 s
提交时间	2016-03-22 17:17:05	内存使用	52.88 MiB

#define maxn 5010ul
#define maxe 3000010ul

#include <queue>
#include <stdio.h>
#include <string.h>

struct pii{int x,y;};
struct Edge{int u,v,nx,w,c;};
Edge edge[maxe];
int n,ec=1,headlist[maxn],S,T2,T,cnt,min_cost,A,B,f,fA,fB,tot,dis[maxn],flow[maxn],from[maxn],id[maxn][2],seq[maxn],must[maxn];
bool ex[maxn];
const int inf=0x3fffffff;
std::queue<int> que;

void Add_Edge(int u,int v,int w,int c){
    edge[++ec]=(Edge){u,v,headlist[u],w,c};
    headlist[u]=ec;
    return;
}

void Add(int u,int v,int w,int c){
    Add_Edge(u,v,w,c);
    Add_Edge(v,u,0,-c);
    return;
}

bool spfa(int &cost){
    memset(dis,0x2f,sizeof(dis));
    memset(flow,0,sizeof(flow));
    memset(from,0,sizeof(from));
    memset(ex,0,sizeof(ex));
    que.push(S);flow[S]=inf,dis[S]=0;
    while(!que.empty()){
        int p=que.front();que.pop();ex[p]=false;
        for(int i=headlist[p];i;i=edge[i].nx) if(edge[i].w>0&&dis[edge[i].v]>dis[p]+edge[i].c){
            dis[edge[i].v]=dis[p]+edge[i].c,from[edge[i].v]=i;
            flow[edge[i].v]=std::min(flow[p],edge[i].w);
            if(!ex[edge[i].v]) ex[edge[i].v]=true,que.push(edge[i].v);
        }
    }
    if(dis[T]>(int)(1e8)) return false;
    cost+=flow[T]*dis[T];
    for(int i=T;i;i=edge[from[i]].u) edge[from[i]].w-=flow[T],edge[from[i]^1].w+=flow[T];
    return true;
}

int mcmf(){
    int ans=0;
    while(spfa(ans));
    return ans;
}

bool check(int mid){
	ec=1;
	memset(headlist,0,sizeof(headlist));
	for(int i=1,x;i<=n;i++){
		x=seq[i];
        Add(S,id[i][0],inf,f);
		Add(id[i][0],id[i][1],x,-100000),must[i]=ec-1;
		if(i!=n) Add(id[i][0],id[i+1][0],inf,0);
		if(i+A<=n) Add(id[i][1],id[i+A][0],inf,fA);
		if(i+B<=n) Add(id[i][1],id[i+B][0],inf,fB);
		Add(id[i][1],T2,inf,0);
	}
	Add(T2,T,mid,0);min_cost=mcmf();
	for(int i=1;i<=n;i++) if(edge[must[i]].w!=0) return false;
	return true;
}

int main(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&seq[i]),tot+=seq[i];
	scanf("%d%d%d%d%d",&f,&A,&fA,&B,&fB);
	for(int i=1;i<=n;i++) id[i][0]=++cnt,id[i][1]=++cnt;T2=++cnt,T=++cnt;
	int L=0,R=tot,mid,a1,a2,mid2,ans_lower=-1,ans=0x2fffffff;
	while(L<=R){
		mid=(L+R)>>1;
		if(check(mid)) R=mid-1,ans_lower=mid;
		else L=mid+1;
	}
	L=ans_lower,R=tot;
	while(L<=R){
		mid=(L+R)>>1,mid2=(L+mid)>>1;
		check(mid),a1=min_cost;
		check(mid2),a2=min_cost;
		ans=std::min(ans,std::min(a1,a2));
		if(a1>a2) R=mid-1;
		else L=mid2+1;
	}
	if(ans!=-1) printf("%d",ans+tot*100000);
	else printf("%d",tot*f);
	return 0;
}