DTTUI1 - Cái túi 1

Tác giả: RR

Ngôn ngữ: Pascal

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       40;

var
  f1,f2         :       text;
  n,m           :       longint;
  res           :       int64;
  v,w           :       array[1..MAXN] of longint;

  n1,n2         :       longint;
  sv1,sv2,
  sw1,sw2       :       array[0..1050000] of longint;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n,m);
      for i:=1 to n do
        read(f1,w[i],v[i]);
    end;

procedure swap(var a,b:longint); inline;
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort1(l,r:longint); inline;
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=sw1[l+random(r-l+1)];
      repeat
        while sw1[i]<mid do inc(i);
        while sw1[j]>mid do dec(j);
        if i<=j then
          begin
            swap(sv1[i],sv1[j]);
            swap(sw1[i],sw1[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort1(i,r);
      if l<j then sort1(l,j);
    end;

procedure sort2(l,r:longint); inline;
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=sw2[l+random(r-l+1)];
      repeat
        while sw2[i]<mid do inc(i);
        while sw2[j]>mid do dec(j);
        if i<=j then
          begin
            swap(sv2[i],sv2[j]);
            swap(sw2[i],sw2[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort2(i,r);
      if l<j then sort2(l,j);
    end;

procedure solve;
    var
      i,j,bit,nn,m1:longint;
    begin
      nn:=n shr 1;
      n1:=1 shl nn;
      n2:=1 shl (n-nn);

      for i:=0 to n1-1 do
        for bit:=1 to nn do
          if (i shr (bit-1)) and 1=1 then
            begin
              inc(sv1[i],v[bit]);
              inc(sw1[i],w[bit]);
            end;

      for i:=0 to n2-1 do
        for bit:=1 to n-nn do
          if (i shr (bit-1)) and 1=1 then
            begin
              inc(sv2[i],v[bit+nn]);
              inc(sw2[i],w[bit+nn]);
            end;

      sort1(0,n1-1);
      sort2(0,n2-1);

      j:=0; res:=0; m1:=sv1[j];
      for i:=n2-1 downto 0 do
        begin
          while (j<n1-1) and (sw1[j+1]+sw2[i]<=m) do
            begin
              inc(j);
              m1:=max(m1,sv1[j]);
            end;
          if (sw1[j]+sw2[i]<=m) and (m1+sv2[i]>res) then res:=m1+sv2[i];
        end;
      writeln(f2,res);
    end;

begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
  inp;
  solve;
  close(f1); close(f2);
end.

Download