啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!!!!!!!
烦死啦!!!!!
三分加贪心。。。。
这一题的贪心是真的难写。。。
三分函数为\(f(x)\)表示购买\(x\)个玩具的最小总花费。
可以用一些奇奇怪怪的方法证明七为单峰函数。。。
然后三分\(x\)
贪心先用慢洗的,再用快洗的,就是慢的从前往后,快的从后往前。
前一个用指针,后一个用并查集维护。。。(并查集是为了加速)
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
const int N=5e5+10;
int D,N1,N2,C1,C2,Tc,T[N],fa[N],Ned[N];
inline int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);}
inline int f(int x)
{
int Sum=x*Tc,Top2=1,Top1=0;
for(int i=1;i<=D;i++) Ned[i]=T[i],fa[i]=i;
for(int i=1;i<=D;i++)
{
int Now=Ned[i];
if(x>=Now) {x-=Now;Now=0;continue;}
else Now-=x,x=0; Top1=i-N1;
while(Top2<=i-N2)
if(Ned[Top2]>=Now) {Ned[Top2]-=Now,Sum+=Now*C2,Now=0;break;}
else Now-=Ned[Top2],Sum+=Ned[Top2]*C2,Ned[Top2++]=0;
if(!Now) continue;
while(Top2<=Top1)
if(Ned[Top1]>=Now) {Ned[Top1]-=Now,Sum+=Now*C1,Now=0;break;}
else Now-=Ned[Top1],Sum+=Ned[Top1]*C1,Ned[Top1]=0,fa[Top1]=Find(Top1-1),Top1=fa[Top1];
if(Now>0) return 1e9;
}
return Sum;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
int l=1,r=0;D=read(),N1=read(),N2=read();
C1=read(),C2=read(),Tc=read();
if(N1>N2) swap(N1,N2),swap(C1,C2);
if(C1<C2) C2=C1,N2=N1;
for(int i=1;i<=D;i++) T[i]=read(),r+=T[i];
while(r-l>=5)
{
int lmid=l+(r-l+1)/3,rmid=l+(r-l+1)*2/3;
int Yl=f(lmid),Yr=f(rmid);
if(Yl!=1e9&&Yl<=Yr) r=rmid;
else l=lmid;
}
int ans=f(l);for(int i=l+1;i<=r;i++) ans=min(ans,f(i));
printf("%d",ans);
}