NTHUGE - Cái túi 3
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
const fi='';
maxn=16;
maxk=1 shl maxn;
var n,nn,mxx,mx:longint;
w,v:array[1..maxn shl 1] of int64;
f,g:array[1..maxk] of int64;
a:array[1..maxk shl 2] of int64;
ww,vv,re,l,r:int64;
function max(x,y:int64):int64;
begin
if x>y then max:=x else max:=y;
end;
procedure rf;
var i,j:longint; t:int64;
begin
read(n,l,r);
for i:=1 to n do read(w[i],v[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if w[i]>w[j] then
begin
t:=w[i]; w[i]:=w[j]; w[j]:=t;
t:=v[i]; v[i]:=v[j]; v[j]:=t;
end;
end;
procedure sort(l,r:longint);
var i,j:longint; x,y,t:int64;
begin
i:=l; j:=r; x:=f[(i+j) shr 1]; t:=g[(i+j) shr 1];
repeat
while (f[i]<x) or ((f[i]=x) and (g[i]>t)) do i:=i+1;
while (f[j]>x) or ((f[j]=x) and (g[j]<t)) do j:=j-1;
if i<=j then
begin
y:=f[i]; f[i]:=f[j]; f[j]:=y;
y:=g[i]; g[i]:=g[j]; g[j]:=y;
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 add(node,l,r,x:longint;val:int64);
var mid:longint;
begin
if (l=r) and (l=x) then a[node]:=a[node]+val
else
begin
mid:=(l+r) shr 1;
if x<=mid then add(node shl 1,l,mid,x,val)
else add(node shl 1+1,mid+1,r,x,val);
a[node]:=max(a[node shl 1],a[node shl 1+1]);
end;
end;
procedure edit;
var num,i:longint;
begin
num:=1;
for i:=2 to mxx do
if f[i]<>f[num] then
begin
num:=num+1;
f[num]:=f[i];
g[num]:=g[i];
end;
mxx:=num;
end;
function bs(x:int64):longint;
var l,r,m,i:longint;
begin
l:=1; r:=mxx; bs:=0;
while l<=r do
begin
m:=(l+r) shr 1;
if f[m]=x then break;
if f[m]<x then l:=m+1
else r:=m-1;
end;
for i:=m-1 to m+1 do
if (i>0) and (i<=mxx) and (f[i]>=x) then
begin
bs:=i; exit;
end;
end;
function bss(x:int64):longint;
var l,r,m,i:longint;
begin
l:=1; r:=mxx; bss:=0;
while l<=r do
begin
m:=(l+r) shr 1;
if f[m]=x then break;
if f[m]<x then l:=m+1
else r:=m-1;
end;
for i:=m+1 downto m-1 do
if (i>0) and (i<=mxx) and (f[i]<=x) then
begin
bss:=i; exit;
end;
end;
procedure findmax(node,l,r,x,y:longint;var val:int64);
var mid:longint; t,u:int64;
begin
if (l=x) and (r=y) then val:=a[node]
else
begin
mid:=(l+r) shr 1; t:=-1; u:=-1;
if x<=mid then findmax(node shl 1,l,mid,x,min(y,mid),t);
if mid<y then findmax(node shl 1+1,mid+1,r,max(x,mid+1),y,u);
val:=max(t,u);
end;
end;
procedure pr;
var i,j,nnn,x,y:longint; val:int64;
begin
nn:=(n+1) shr 1;
mxx:=1 shl nn;
for i:=1 to mxx-1 do
for j:=1 to nn do
if i shr (j-1) and 1=1 then
begin
f[i+1]:=f[i+1]+w[j];
g[i+1]:=g[i+1]+v[j];
end;
sort(1,mxx);
edit;
for i:=1 to mxx do
add(1,1,mxx,i,g[i]);
nnn:=n-nn;
mx:=1 shl nnn-1;
re:=0;
for i:=0 to mx do
begin
ww:=0; vv:=0;
for j:=1 to nnn do
if i shr (j-1) and 1=1 then
begin
ww:=ww+w[nn+j];
if ww>r then break;
vv:=vv+v[nn+j];
end;
if (ww>r) or (vv+a[1]<=re) then continue;
if ww>=l then x:=1
else x:=bs(l-ww);
y:=bss(r-ww);
val:=0;
if x>0 then findmax(1,1,mxx,x,y,val);
re:=max(re,val+vv);
end;
writeln(re);
end;
begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.