比赛 20120710 评测结果 AAAAWATATA
题目名称 快餐问题 最终得分 70
用户昵称 fuhao 运行时间 2.030 s
代码语言 Pascal 内存使用 0.75 MiB
提交时间 2012-07-10 11:50:38
显示代码纯文本
program meal;
const maxn=11;
var
 a,b,c,p1,p2,p3,ans,n,i,j,x,y,nx,ny,many,r,cuple,l,numa,numb,numc:longint;
 f:array[0..maxn,0..100,0..100] of longint;
 sum,t:array[0..maxn] of longint;
 ok:array[0..maxn,0..100,0..100] of boolean;
begin
 assign(input,'meal.in'); reset(input);
 assign(output,'meal.out'); rewrite(output);
 readln(a,b,c);
 readln(p1,p2,p3);
 readln(n);
 for i:=1 to n do read(t[i]);
 ans:=0; cuple:=a*p1+b*p2+c*p3;
 numa:=0; numb:=0; numc:=0;
 for i:=1 to n do
  begin
   while t[i]>=cuple do
    begin
      if numa+a>100 then
       begin
        writeln(ans);
        close(input); close(output);
        halt;
       end;
      if numb+b>100 then
       begin
        writeln(ans);
        close(input); close(output);
        halt;
       end;
      if numc+c>100 then
       begin
        writeln(ans);
        close(input); close(output);
        halt;
       end;
     numa:=numa+a; numb:=numb+b; numc:=numc+c;
     ans:=ans+1; t[i]:=t[i]-cuple;
    end;
   sum[i]:=sum[i-1]+t[i];
  end;
 ok[0,0,0]:=true;
 for i:=1 to n do
  for nx:=0 to sum[i-1] div p1 do
   for ny:=0 to sum[i-1] div p2 do
    if ok[i-1,nx,ny] then
     for x:=0 to t[i] div p1 do
      for y:=0 to t[i] div p2 do
       if x*p1+y*p2<=t[i] then
       begin
        l:=x+nx; if l>100 then l:=100;
        r:=y+ny; if r>100 then r:=100;
        if f[i,l,r]<f[i-1,nx,ny]+(t[i]-x*p1-y*p2) div p3 then
         f[i,l,r]:=f[i-1,nx,ny]+(t[i]-x*p1-y*p2) div p3;
        ok[i,l,r]:=true;
       end;
  many:=0;
  for i:=0 to 100 do
   for j:=0 to 100 do
    if ok[n,i,j] then
    begin
     ny:=maxlongint;
     x:=i div a; y:=j div b; nx:=f[n,i,j] div c;
     if ny>x then ny:=x;
     if ny>y then ny:=y;
     if ny>nx then ny:=nx;
     if many<ny then many:=ny;
    end;
  for i:=1 to many do
   begin
      if numa+a>100 then
       begin
        writeln(ans);
        close(input); close(output);
        halt;
       end;
      if numb+b>100 then
       begin
        writeln(ans);
        close(input); close(output);
        halt;
       end;
      if numc+c>100 then
       begin
        writeln(ans);
        close(input); close(output);
        halt;
       end;
     ans:=ans+1;
     numa:=numa+a; numb:=numb+b; numc:=numc+c;
   end;
  writeln(ans);
  close(input); close(output);
end.