Cod sursa(job #1002785)

Utilizator wollyFusy Wool wolly Data 28 septembrie 2013 20:20:12
Problema Energii Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.97 kb
type tabval=array[1..1100,1..1100] of longint;
	tabgred=array[1..1100] of real;
var a,b:text;
	t:tabval;
	u:tabgred;
	i,n,sum,sy,sz,sx:longint;
	
procedure qs(s,f:longint);
var x,i,j,m:longint;
	y,p:real;
begin
i:=s;
j:=f;
m:=(s+f) div 2;
p:=u[m];

while u[i]<p do i:=i+1;
while u[j]>=p do j:=j-1;

if (i<=j) then
begin
x:=t[i,1];
t[i,1]:=t[j,1];
t[j,1]:=x;
x:=t[i,2];
t[i,2]:=t[j,2];
t[j,2]:=x;
y:=u[i];
u[i]:=u[j];
u[j]:=y;
i:=i+1;
j:=j-1;
end;

if j-s>1 then qs(s,j);
if f-i>1 then qs(i,f);

end;	
	
begin
assign(a,'energii.in');
reset(a);
assign(b,'energii.out');
rewrite(b);

read(a,n,sum);
for i:=1 to n do
begin
read(a,t[i,1],t[i,2]);
u[i]:=t[i,2]/t[i,1];
end;
qs(1,n);

for i:=1 to n do
sx:=sx+t[i,1];
sz:=0;
sy:=0;
i:=1;

if sx<sum then writeln(b,'-1') else
while sz<sum do
begin
if (u[i]>-1) or (i>n) then
begin
sy:=sy+t[i,2];
sz:=sz+t[i,1];
u[i]:=-1;
end;
i:=i+1;
end;

writeln(b,sy);

close(a);
close(b);
end.