DTTUI1 - Cái túi 1

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=40;
      maxc=1048575;
var n,re,m,mid,max,num:longint;
    v,w:array[1..40] of longint;
    f,g:array[0..maxc] of longint;

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

procedure calc;
var i,j:longint;
begin
     max:=1 shl mid-1;
     for i:=1 to max do
         for j:=0 to mid-1 do
             if (i shr j) and 1=1 then
             begin
                  f[i]:=f[i]+w[j+1];
                  g[i]:=g[i]+v[j+1];
             end;
end;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=f[(i+j) shr 1]; y:=g[(i+j) shr 1];
     repeat
           while (f[i]<x) or ((f[i]=x) and (g[i]>y)) do i:=i+1;
           while (f[j]>x) or ((f[j]=x) and (g[j]<y)) do j:=j-1;
           if i<=j then
           begin
                t:=f[i]; f[i]:=f[j]; f[j]:=t;
                t:=g[i]; g[i]:=g[j]; g[j]:=t;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure edit;
var i:longint;
begin
     num:=0;
     for i:=1 to max do
         if g[i]>g[num] then
         begin
              num:=num+1;
              f[num]:=f[i];
              g[num]:=g[i];
         end;
end;

function bs(t:longint):longint;
var l,r,md,i:longint;
begin
     l:=0; r:=num;
     while l<=r do
     begin
          md:=(l+r) shr 1;
          if f[md]=t then break;
          if f[md]<t then l:=md+1
          else r:=md-1;
     end;
     if f[md]=t then bs:=md
     else
     begin
          for i:=md+1 downto md-1 do
              if (i>=0) and (i<=num) and (f[i]<=t) then
              begin
                   bs:=i; exit;
              end;
     end;
end;

procedure pr;
var i,l,ww,vv,j,x:longint;
begin
     mid:=(n+1) shr 1;
     calc;
     sort(1,max);
     edit;
     l:=mid+1; mid:=n-mid;
     max:=1 shl mid-1;
     re:=0;
     for i:=0 to max do
     begin
          ww:=0; vv:=0;
          for j:=0 to mid-1 do
              if (i shr j) and 1=1 then
              begin
                   ww:=ww+w[l+j];
                   vv:=vv+v[l+j];
              end;
          if ww<=m then
          begin
               x:=bs(m-ww);
               if vv+g[x]>re then re:=vv+g[x];
          end;
     end;
end;


procedure wf;
begin
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     wf;
     close(input); close(output);
end.

Download