BZOJ1042 Coins

{$INLINE ON,R-}
program bzoj1042;
 
const n=4;
      maxm=100017;
 
var f,g,s:array[0..maxm] of int64;
    r2,r3:array[0..maxm] of longint;
    m,opcnt,w1,c1,w2,c2,w3,c3,w4,c4,mdw1,mdw4,maxw:longint;
 
function min(i,j:longint):longint; inline; begin
if i<j then exit(i) else exit(j);  end;
function max(i,j:longint):longint; inline; begin
if i>j then exit(i) else exit(j);  end;
 
function dp:int64;
var i,j,k,upper:longint;
    r:^longint;
begin
fillchar(f,(m+1)<<4,0);
for j:=0 to min(c1,mdw1) do f[j*w1]:=1;
fillchar(s,sizeof(s),0); r:=@r2[0]; for j:=0 to m do begin
        inc(r); inc(s[r^],f[j]);
        k:=j-(c2+1)*w2; if k>=0 then dec(s[r^],f[k]);
        g[j]:=s[r^];
end;
fillchar(s,sizeof(s),0); r:=@r3[0]; for j:=0 to m do begin
        inc(r); inc(s[r^],g[j]);
        k:=j-(c3+1)*w3; if k>=0 then dec(s[r^],g[k]);
        f[j]:=s[r^];
end;
dp:=0; for i:=0 to min(c4,mdw4) do inc(dp,f[m-i*w4]);
end;
 
procedure work;
var i,j:longint;
begin
readln(w1,w2,w3,w4,opcnt);
for i:=1 to maxm do if r2[i-1]=w2-1 then r2[i]:=0 else r2[i]:=r2[i-1]+1;
for i:=1 to maxm do if r3[i-1]=w3-1 then r3[i]:=0 else r3[i]:=r3[i-1]+1;
maxw:=max(max(w1,w2),max(w3,w4));
while opcnt>0 do begin dec(opcnt);
        readln(c1,c2,c3,c4,m);
        mdw1:=m div w1; mdw4:=m div w4;
        writeln(dp);
end;
end;
 
begin
work;
end.