记录编号	393323	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2017-04-10 17:45:51	内存使用	0.32 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 210, INF = 0x7fffffff;

const inline int in(void){
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp))tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct EDGE{
	int fr, to, ne;
	int cap, w;
	
	EDGE(){;}
	EDGE(int a, int b, int c, int d, int e){
		fr = a, to = b, ne = c, cap = d, w = e;
	}
};

inline void add_edge(int fr, int to, int cap, int w);
int SPFA();

vector<EDGE> edge;
int head[MAXN << 1];
bool inq[MAXN << 1];
int dis[MAXN << 1], pre[MAXN << 1];
int S, T;
int N, r[MAXN], ans;
int p, m, f, n, s;

int main(){
#ifndef LOCAL
	freopen("napkin.in", "r", stdin);
	freopen("napkin.out", "w", stdout);
#endif
	memset(head, 0xff, sizeof(head));
	
	N = in();
	for(int i = 1; i <= N; ++i)r[i] = in();
	p = in(), m = in(), f = in(), n = in(), s = in();
	
	S = 0, T = N * 2 + 1;
	
	for(int i = 1; i <= N; ++i){
		add_edge(S, i, r[i], 0);
		add_edge(i + N, T, r[i], 0);
	}
	
	for(int i = 1; i < N; ++i){
		add_edge(i, i + 1, INF, 0);
	}
	
	for(int i = 1; i + m <= N; ++i){
		add_edge(i, i + m + N, INF, f);
	}
	
	for(int i = 1; i + n <= N; ++i){
		add_edge(i, i + n + N, INF, s);
	}
	
	for(int i = 1; i <= N; ++i){
		add_edge(S, i + N, INF, p);
	}
	
	int tmp;
	while(tmp = SPFA()){
		ans += tmp;
	}
	
	printf("%d", ans);
	
	return 0;
}

inline void add_edge(int fr, int to, int cap, int w){
	edge.push_back(EDGE(fr, to, head[fr], cap, w)), head[fr] = edge.size() - 1;
	edge.push_back(EDGE(to, fr, head[to], 0, -w)), head[to] = edge.size() - 1;
	return ;
}

int SPFA(){
	memset(dis, 0x7f, sizeof(dis));
	memset(inq, 0x00, sizeof(inq));
	memset(pre, 0xff, sizeof(pre));
	
	queue<int> que;
	
	que.push(S);
	inq[S] = true; dis[S] = 0;
	
	int now, to;
	while(!que.empty()){
		now = que.front();
		que.pop();
		inq[now] = false;
		for(int i = head[now]; i != -1; i = edge[i].ne){
			to = edge[i].to;
			if(edge[i].cap <= 0 || dis[now] + edge[i].w >= dis[to])continue;
			dis[to] = dis[now] + edge[i].w;
			pre[to] = i;
			if(inq[to])continue;
			que.push(to);
			inq[to] = true;
		}
	}
	
	if(pre[T] == -1)return 0;
	
	now = pre[T];
	int min_flow = INF;
	while(now != -1){
		min_flow = min(min_flow, edge[now].cap);
		now = pre[edge[now].fr];
	}
	
	now = pre[T];
	while(now != -1){
		edge[now].cap -= min_flow;
		edge[now ^ 1].cap += min_flow;
		now = pre[edge[now].fr];
	}
	
	return min_flow * dis[T];
}