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.

Download