Cod sursa(job #159792)

Utilizator TudorutzuMusoiu Tudor Tudorutzu Data 14 martie 2008 13:34:27
Problema Heavy metal Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.03 kb
var a,best,b:array[0..100000] of longint;
    f,g:text;
    n,i,j:longint;
procedure quick(s,d:longint);
var i,j,w,x:longint;
begin
     i:=s; j:=d; x:=b[(s+d)div 2];
     repeat
          while b[i]<x do inc(i);
          while b[j]>x do dec(j);
          if i<=j then
          begin
               w:=b[i]; b[i]:=b[j]; b[j]:=w;
               w:=a[i]; a[i]:=a[j]; a[j]:=w;
               inc(i); dec(j);
          end
     until i>j;
     if i<d then quick(i,d);
     if j>s then quick(s,j);
end;
begin
     assign(f,'heavymetal.in'); reset(f);
     assign(g,'heavymetal.out'); rewrite(g);
     readln(f,n);
     for i:=1 to n do readln(f,a[i],b[i]);
     quick(1,n);
     for i:=1 to b[n] do
     begin
          best[i]:=best[i-1];
          for j:=1 to n do
          begin
               if b[j]=i then
               begin
                    if best[i]<b[a[j]]+(b[j]-a[j]) then best[i]:=best[a[j]]+(b[j]-a[j]);
               end
          end;
     end;
     writeln(g,best[b[n]]);
     close(g);
end.