比赛 |
20101025 |
评测结果 |
AAAAAAAAAA |
题目名称 |
逛街 |
最终得分 |
100 |
用户昵称 |
Achilles |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2010-10-25 20:08:44 |
显示代码纯文本
program shop;
var
ans,n,x,y,i,j,top,topt,now,last:longint;
sz:array[0..300,1..4]of longint;
tab:array[0..1,0..1000,0..100]of longint;
cut:array[1..100000,1..2]of longint;
hx:array[0..1000,0..100]of boolean;
begin
assign(input,'shop.in');
assign(output,'shop.out');
reset(input);
rewrite(output);
readln(n,x,y);
for i:=1 to n do
readln(sz[i,1],sz[i,2],sz[i,3],sz[i,4]);
top:=1;
cut[1,1]:=0;
cut[1,2]:=0;
fillchar(tab,sizeof(tab),0);
now:=0;
last:=1;
fillchar(hx,sizeof(hx),true);
for i:=1 to n do
begin
topt:=top;
for j:=1 to top do
begin
if (cut[j,1]+sz[i,1]<=x)and(cut[j,2]+sz[i,2]<=y) then begin
if tab[last,cut[j,1],cut[j,2]]+sz[i,3]>tab[now,cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]] then begin
tab[now,cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]]:=tab[last,cut[j,1],cut[j,2]]+sz[i,3];
if hx[cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]] then begin
topt:=topt+1;
cut[topt,1]:=cut[j,1]+sz[i,1];
cut[topt,2]:=cut[j,2]+sz[i,2];
hx[cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]]:=false;
end;
end;
end;
if (cut[j,1]+sz[i,1]*sz[i,4]<=x)and(cut[j,2]+sz[i,2]*sz[i,4]<=y) then begin
if tab[last,cut[j,1],cut[j,2]]+sz[i,3]*sz[i,4]>tab[now,cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]] then begin
tab[now,cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]]:=tab[last,cut[j,1],cut[j,2]]+sz[i,3]*sz[i,4];
if hx[cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]] then begin
topt:=topt+1;
cut[topt,1]:=cut[j,1]+sz[i,1]*sz[i,4];
cut[topt,2]:=cut[j,2]+sz[i,2]*sz[i,4];
hx[cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]]:=false;
end;
end;
end;
end;
for j:=1 to top do
if tab[last,cut[j,1],cut[j,2]]>tab[now,cut[j,1],cut[j,2]] then tab[now,cut[j,1],cut[j,2]]:=tab[last,cut[j,1],cut[j,2]];
top:=topt;
now:=(now+1)mod 2;
last:=(last+1)mod 2;
end;
ans:=0;
for i:=1 to top do
if tab[last,cut[i,1],cut[i,2]]>ans then ans:=tab[last,cut[i,1],cut[i,2]];
writeln(ans);
close(input);
close(output);
end.