记录编号	167931	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Nov08]玩具	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.362 s
提交时间	2015-06-29 19:39:08	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=100010;
const int INF=0x7fffffff/2;
int N;
int price;
int slow_cost,slow_wait,fast_cost,fast_wait;
int need[SIZEN]={0};
deque<pair<int,int> > can_slow,can_fast,late;//first是日期,second是个数
int calc(int buy){//购买buy个
	int ans=buy*price;
	can_fast.clear();can_slow.clear();late.clear();
	for(int i=1;i<=N;i++){
		while(!late.empty()&&late.front().first<=i-fast_wait){
			can_fast.push_back(late.front());
			late.pop_front();
		}
		while(!can_fast.empty()&&can_fast.front().first<=i-slow_wait){
			can_slow.push_back(can_fast.front());
			can_fast.pop_front();
		}
		int now=need[i];
		int t=min(now,buy);
		now-=t,buy-=t;
		while(now&&!can_slow.empty()){
			t=min(now,can_slow.back().second);
			ans+=t*slow_cost;
			now-=t,can_slow.back().second-=t;
			if(!can_slow.back().second) can_slow.pop_back();
		}
		while(now&&!can_fast.empty()){
			t=min(now,can_fast.back().second);
			ans+=t*fast_cost;
			now-=t,can_fast.back().second-=t;
			if(!can_fast.back().second) can_fast.pop_back();
		}
		if(now) return INF;
		late.push_back(make_pair(i,need[i]));
	}
	return ans;
}
void work(void){
	int l=0,r=0;
	for(int i=1;i<=N;i++) r+=need[i];
	while(r-l>2){
		int m1=(2*l+r)/3,m2=(l+2*r+2)/3;
		int f1=calc(m1),f2=calc(m2);
		if(f1>=f2) l=m1;
		else r=m2;
	}
	int ans=INF;
	for(int i=l;i<=r;i++) ans=min(ans,calc(i));
	printf("%d\n",ans);
}
void read(void){
	scanf("%d",&N);
	scanf("%d%d",&fast_wait,&slow_wait);
	scanf("%d%d",&fast_cost,&slow_cost);
	if(fast_wait>slow_wait){
		swap(fast_wait,slow_wait);
		swap(fast_cost,slow_cost);
	}
	if(slow_cost>fast_cost){
		slow_wait=fast_wait;
		slow_cost=fast_cost;
	}
	scanf("%d",&price);
	for(int i=1;i<=N;i++) scanf("%d",&need[i]);
}
int main(){
	freopen("toy.in","r",stdin);
	freopen("toy.out","w",stdout);
	read();
	work();
	return 0;
}