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.