Cod sursa(job #137526)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 17 februarie 2008 12:33:25
Problema Heavy metal Scor 40
Compilator fpc Status done
Runda preONI 2008, Runda 4, Clasele 5-8 Marime 1.34 kb
type timp=record
     x,y:longint;
     end;

var a,b:array[0..100000] of timp;
    f,g:text;
    i,n,max,j:longint;
    c:array[0..100000] of longint;

procedure inter(st,mij,dr:longint);
 var i,j,k,t:longint;
 begin
  for i:=st to dr do
   b[i]:=a[i];
  i:=st;
  j:=mij+1;
  k:=st;
  while (i<=mij) and (j<=dr) do
   if b[i].x<b[j].x then begin
    a[k]:=b[i];
    inc(i);
    inc(k);
   end
   else
    if (b[i].x=b[j].x) and (b[i].y<b[j].y) then begin
     a[k]:=b[i];
     inc(i);
     inc(k);
    end
    else begin
     a[k]:=b[j];
     inc(k);
     inc(j);
    end;
  for t:=i to mij do begin
   a[k]:=b[t];
   inc(k);
  end;
  for t:=j to dr do begin
   a[k]:=b[t];
   inc(k);
  end;
 end;

procedure merge(st,dr:longint);
 var mij:longint;
 begin
  if st<dr then begin
   mij:=(st+dr) shr 1;
   merge(st,mij);
   merge(mij+1,dr);
   inter(st,mij,dr);
  end;
 end;

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