记录编号	457543	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Nov08]玩具	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.307 s
提交时间	2017-10-08 18:01:50	内存使用	1.46 MiB

#pragma GCC optimize("O3")
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
using namespace std;
int d,n1,n2,c1,c2,t,a[N],sum[N],f[N];
int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
	return sum*f;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline int check(int x)
{
	int s=x*t,top1=1,top2=0;
	for(int i=1;i<=d;i++)sum[i]=a[i],f[i]=i;
	for(int i=1;i<=d;i++)
	{
		int k=sum[i];
		if(x>=k){x-=k;k=0;continue;}else k-=x,x=0;
		top2=i-n2;
		while(top1<=i-n1)
		{
			if(sum[top1]>=k){sum[top1]-=k;s+=k*c1;k=0;break;}
			else{k-=sum[top1];s+=sum[top1]*c1;sum[top1]=0;top1++;}
		}
		if(k==0)continue;
		while(top1<=top2)
		{
			if(sum[top2]>=k){sum[top2]-=k;s+=k*c2;k=0;break;}
			else{k-=sum[top2];s+=sum[top2]*c2;sum[top2]=0;f[top2]=find(top2-1);top2=f[top2];}
		}
		if(k>0)return 1000000000;
	}
	return s;
}
int main()
{
	freopen("toy.in","r",stdin);
	freopen("toy.out","w",stdout);
	scanf("%d%d%d%d%d%d",&d,&n1,&n2,&c1,&c2,&t);int h=0;
	if(n1<n2){swap(n1,n2);swap(c1,c2);}
	if(c1>c2)c1=c2,n1=n2;
	for(int i=1;i<=d;i++)a[i]=read(),h+=a[i];
	int l=1,r=h,mid,mmid,ans=1000000000;
	while(l<=r-3)
	{
		int k=r-l+1;mid=l+k/3;mmid=l+(k*2)/3;
		int s1=check(mid),s2=check(mmid);
		if(s1<s2)r=mmid;
		else l=mid;
	}
	for(int i=l;i<=r;i++)ans=min(ans,check(i));
	printf("%d\n",ans);
}