Cod sursa(job #137569)

Utilizator marius21Petcu Marius marius21 Data 17 februarie 2008 12:42:03
Problema Heavy metal Scor 40
Compilator fpc Status done
Runda preONI 2008, Runda 4, Clasele 5-8 Marime 1.27 kb
type band=record
   cncl:boolean;
   a,b:longint;
   end;
var a,tmp: array[1..100001] of band;
b:array[1..100000] of longint;
f,g:text;
s,i,n,max,j,max2:longint;

procedure sort(si,sj:longint);
var mid,i,j,t:longint;
begin
if si<sj then begin
   mid:=(si+sj)div 2;
   sort(si,mid);
   sort(mid+1,sj);
   i:=si;
   j:=mid+1;
   t:=si;
   while (i<=mid) and (j<=sj) do
      if a[i].a<=a[j].a then  begin
         tmp[t]:=a[i];
         inc(t);
         inc(i);
         end else
         begin
         tmp[t]:=a[j];
         inc(t);
         inc(j);
         end;
   while i<=mid do begin
         tmp[t]:=a[i];
         inc(t);
         inc(i);
         end;
   while j<=sj do begin
         tmp[t]:=a[j];
         inc(t);
         inc(j);
         end;
   for i:=si to sj do
      a[i]:=tmp[i];
   end;
end;

begin
assign(f,'heavymetal.in');
assign(g,'heavymetal.out');
reset(f);
rewrite(g);
read(f,n);
for i:=1 to n do
   read(f,a[i].a,a[i].b);
sort(1,n);
b[1]:=a[1].b-a[1].a;
max2:=0;
for i:=2 to n do begin
   max:=0;
   for j:=i-1 downto 1 do
      if (a[i].a>=a[j].b) and (b[j]>max) then
         max:=b[j];
   b[i]:=max+a[i].b-a[i].a;
   if max2<b[i] then max2:=b[i];
   end;
writeln(g,max2);
close(f);
close(g);
end.