Cod sursa(job #167230)

Utilizator constantin02constantin constantin02 Data 29 martie 2008 11:37:24
Problema Heavy metal Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.62 kb
type trio=record
     a,b,s:longint;
     end;
var fi,fo:text;
    n,i:longint;
    v:array[0..100000]of trio;

procedure down(i,n:longint);
var fiu,tata:longint;
    l:trio;
begin
  l:=v[i]; tata:=i; fiu:=i shl 1;
  while fiu<=n do
    begin
      if fiu<n then
        if v[fiu].b<v[fiu+1].b then inc(fiu);
      if l.b<v[fiu].b then
        begin
          v[tata]:=v[fiu];
          tata:=fiu;
          fiu:=fiu shl 1;
        end
      else fiu:=n+1;
    end;
  v[tata]:=l;
end;

procedure heapsort;
var i,aux:longint;
    m:trio;
begin
  aux:=n shr 1;
  for i:=aux downto 1 do
    down(i,n);
  for i:=n downto 2 do
    begin
      m:=v[i];
      v[i]:=v[1];
      v[1]:=m;
      down(1,i-1);
    end;
end;

function search(st,dr,vl:longint):longint;
var mij,poz,max:longint;
begin
  max:=0; poz:=0;
  while st<=dr do
    begin
      mij:=(st+dr) shr 1;
      if v[mij].b<=vl then
        begin
          if v[mij].s>max then
            begin
              max:=v[mij].s;
              poz:=mij;
            end;
          st:=mij+1;
        end
      else dr:=mij-1;
    end;
  search:=poz;
end;

procedure solve;
var i,aux:longint;
begin
  for i:=1 to n do
    begin
      aux:=search(1,i-1,v[i].a);
      if v[aux].s+v[i].b-v[i].a>v[i-1].s then
        v[i].s:=v[aux].s+v[i].b-v[i].a
      else
        v[i].s:=v[i-1].s;
    end;
  writeln(fo,v[n].s);
end;

begin
  assign(fi,'heavymetal.in'); reset(fi);
  assign(fo,'heavymetal.out'); rewrite(fo);
  read(fi,n);
  for i:=1 to n do
    read(fi,v[i].a,v[i].b);
  heapsort;
  solve;
  close(fi);
  close(fo);
end.