Pagini recente » Cod sursa (job #683254) | Cod sursa (job #1033140) | Cod sursa (job #2875315) | Cod sursa (job #1102538) | Cod sursa (job #152408)
Cod sursa(job #152408)
{
N - numarul de oi
X - distanta maxima de la care lupul poate alege oi
L - distanta cu care se departeaza oile de lup dupa fiecare alegere
D[] - distanta initiala
A[] - cantitatea de lana
}
program lupu;
type
sir=array[0..100000] of longint;
var
f:text;
d,a,t,h:sir;
j,n,x,l,i,k,tmax,c:longint;
heap:sir;
suma:int64;
function partitie(first,last:longint):longint;
var
q,i,j,aux:longint;
begin
q:=t[first];
i:=first-1;
j:=last+1;
while true do begin
repeat inc(i); until t[i]<=q;
repeat dec(j); until t[j]>=q;
if i<j then begin
aux:=t[i]; t[i]:=t[j]; t[j]:=aux;
aux:=a[i]; a[i]:=a[j]; a[j]:=aux;
aux:=d[i]; d[i]:=d[j]; d[j]:=aux;
end
else begin
partitie:=j;
exit;
end;
end;
end;
procedure qs(first,last:longint);
var
q:longint;
begin
if first<last then begin
q:=partitie(first,last);
qs(first,q);
qs(q+1,last);
end;
end;
function partitie1(first,last:longint):longint;
var
q,aux,i,j:longint;
begin
q:=h[first];
i:=first-1;
j:=last+1;
while true do begin
repeat inc(i); until h[i]>=q;
repeat dec(j); until h[j]<=q;
if i<j then begin
aux:=h[i]; h[i]:=h[j]; h[j]:=aux;
end
else begin
partitie1:=j;
exit;
end;
end;
end;
procedure qs1(first,last:longint);
var
q:longint;
begin
if first<last then begin
q:=partitie1(first,last);
qs1(first,q);
qs1(q+1,last);
end;
end;
begin
assign(f,'lupu.in');
reset(f);
readln(f,n,x,l);
for i:=1 to n do begin
readln(f,d[i],a[i]);
if d[i]>x then t[i]:=0
else t[i]:=1+(x-d[i]) div l;
if t[i]>tmax then tmax:=t[i];
end;
close(f);
qs(1,n);
suma:=0;
j:=1;
c:=0;
for i:=tmax downto 1 do begin
while t[j]=i do begin
inc(c);
h[c]:=a[j];
inc(j);
end;
qs1(1,c);
suma:=suma+h[c];
dec(c);
end;
assign(f,'lupu.out');
rewrite(f);
writeln(f,suma);
close(f);
end.