Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban. Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này Code mẫu của flashmt
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.
Code mẫu của RR
{$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.
|
