Cod sursa(job #163508)

Utilizator vladnVlad Nistorica vladn Data 22 martie 2008 14:18:12
Problema Peste Scor 0
Compilator fpc Status done
Runda preONI 2008, Runda Finala, Clasa a 9-a Marime 1.14 kb
var f,g:text;
    p,t:array[1..51000] of longint;
    i,j,n,k,ttotal,tmax,tmin,sp:longint;
procedure Sort(l, r: Integer);
var
  i, j, y: integer;
  x: real;
begin
  i := l; j := r; x := p[(l+r) DIV 2] / t[(l+r) div 2];
  repeat
    while p[i] / t[i] < x do i := i + 1;
    while x < p[j] / t[j] do j := j - 1;
    if i <= j then
    begin
      y := p[i]; p[i] := p[j]; p[j] := y;
      y := t[i]; t[i] := t[j]; t[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;
begin
assign(f,'peste.in');reset(f);
assign(g,'peste.out');rewrite(g);
readln(f,n,k,ttotal);
for i:=1 to n do begin
    readln(f,p[i],t[i]);
    if t[i]<tmin then tmin:=t[i] else if i=1 then tmin:=t[i];
end;
sort(1,n);
sp:=0;
while (ttotal>0) and (ttotal>=tmin) do begin
      j:=n+1;i:=0;tmax:=0;
      while (j>1) and (i<k) do begin
            dec(j);
            if t[j]<=ttotal then begin
               sp:=sp+p[j];
               inc(i);
               if t[j]>tmax then tmax:=t[j];
            end;
      end;
      ttotal:=ttotal-tmax;
end;
writeln(g,sp);
close(g);
end.