ac1017.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1017;
const
  maxn=20;
  maxw=1000000;
  mask:array[0..7]of byte=(128,64,32,16,8,4,2,1);
var
  stone:array[1..maxn]of longint;
  ok:array[0..maxw shr 3]of byte;
  n,w,i,j,t,m,x:longint;
function min(a,b:longint):longint;
  begin
    if a<b then min:=a else min:=b;
  end;
begin
  repeat
    fillchar(ok,sizeof(ok),0);
    read(n);t:=0;
    for i:=1 to n do begin
      read(stone[i]);
      inc(t,stone[i]);
    end;
    m:=0;ok[0]:=128;
    for i:=1 to n do
      for j:=min(t,maxw) downto stone[i] do begin
        x:=j-stone[i];
        if ok[x shr 3] and mask[x and 7]>0 then begin
          ok[j shr 3]:=ok[j shr 3] or mask[j and 7];
          if (j*2<=t) and (j>m) then m:=j;
        end;
      end;
    writeln(t-m*2);
  until seekeof;
end.